#596 · Subiectul II · Programare

Eliminarea nodurilor de grad minim și numărul muchiilor rămase (nrElem1 și sumaElem)

✓ Rezolvare explicatăBucurești 2020 · nr. 24

Enunț

Se consideră un graf neorientat G cu n vârfuri (2≤n≤30) etichetate 1, 2, …, n. Fișierul atestat.in conține pe prima linie numărul n, iar pe următoarele linii perechi de numere naturale separate prin spațiu, muchiile distincte ale grafului.

Se consideră subprogramele:

nrElem1, cu trei parametri: n (n≤30), v, un tablou unidimensional cu n elemente 0 sau 1, și s, un număr natural. Determină numărul elementelor egale cu 1 din v și îl furnizează prin s;
sumaElem, cu doi parametri: n (2≤n≤30) și a, tablou bidimensional pătratic cu n linii și coloane, elemente numere naturale. Returnează suma elementelor lui a.

a. Scrieți definiția completă a subprogramului nrElem1.

b. Scrieți definiția completă a subprogramului sumaElem.

c. Scrieți un program care citește din atestat.in numărul n și muchiile grafului și, folosind apeluri utile ale subprogramelor nrElem1 și sumaElem, determină nodurile de grad minim, le elimină din graf și scrie în atestat.out numărul de muchii ale subgrafului obținut.

Exemple

`atestat.in`	`atestat.out`	Explicații
`6` `6 1` `2 5` `5 4` `3 4` `6 2` `5 6` `2 4` `6 4`	`6`	Gradele: `1:1, 2:3, 3:1, 4:4, 5:3, 6:4`. Se elimină nodurile `1` și `3` (grad 1); rămân `8 − 2 = 6` muchii
`4` `1 2` `1 3` `2 4` `3 4`	`0`	Toate nodurile au gradul `2`: se elimină toate, nu rămâne nicio muchie

Rezolvare

C++

#include <fstream>
using namespace std;

void nrElem1(int n, int v[], int &s) {
    s = 0;
    for (int i = 0; i < n; i++) s += (v[i] == 1);
}

int sumaElem(int n, int a[31][31]) {
    int s = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) s += a[i][j];
    return s;
}

int main() {
    ifstream f("atestat.in");
    ofstream g("atestat.out");
    int n, x, y, a[31][31] = {}, grad[31], minim, sters[31] = {};
    f >> n;
    while (f >> x >> y) a[x - 1][y - 1] = a[y - 1][x - 1] = 1;   // muchii pana la sfarsitul fisierului

    for (int i = 0; i < n; i++) nrElem1(n, a[i], grad[i]);       // gradul = numarul de 1 de pe linie
    minim = grad[0];
    for (int i = 1; i < n; i++)
        if (grad[i] < minim) minim = grad[i];

    for (int i = 0; i < n; i++) sters[i] = (grad[i] == minim);   // marcam pe baza gradelor initiale
    for (int i = 0; i < n; i++)
        if (sters[i])
            for (int j = 0; j < n; j++) a[i][j] = a[j][i] = 0;   // eliminam linia si coloana

    g << sumaElem(n, a) / 2;             // fiecare muchie apare de doua ori in matrice
    return 0;
}

Exersează mai departe

Probleme cu aceeași tehnică

#595ProgramareRădăcina și matricea de adiacență a unui arbore dat prin vectorul de tați #560ProgramareArbore dat prin vectorul de tați: rădăcina, nodurile cu cei mai mulți fii și frunzele (subprogramul pozitie)#597ProgramareNodurile izolate dintr-un graf dat prin matricea de adiacență (citire și suma)#045ProgramareSă se afişeze indicii coloanelor care au toate elementele impare #048ProgramareSă se afişeze cel mai mare element din matrice şi poziţiile pe care apare #049ProgramareSă se afişeze cel mai mic element din matrice şi poziţiile pe care apare