#597 · Subiectul II · Programare

Nodurile izolate dintr-un graf dat prin matricea de adiacență (citire și suma)

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

Enunț

Fișierul atestat.in conține pe prima linie un număr natural n (2≤n≤20), iar pe următoarele n linii elementele unui tablou bidimensional a cu n linii și n coloane.

Se consideră subprogramele:

citire, cu doi parametri, a și n: citește numerele din atestat.in și furnizează prin a un tablou cu n·n componente din mulțimea {0, 1}, matricea de adiacență a unui graf neorientat;
suma, care primește prin parametrul v un tablou unidimensional de numere naturale și prin parametrul k numărul lui de elemente. Returnează suma elementelor lui v.

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

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

c. Scrieți un program care, folosind apeluri utile ale subprogramelor citire și suma, scrie în atestat.out etichetele nodurilor izolate sau, dacă nu există astfel de noduri, mesajul nu exista noduri izolate.

⚠️ Inconsecvență de scriere. Enunțul cere mesajul „nu există noduri izolate” (cu diacritică), iar exemplul oficial arată nu exista noduri izolate. Rezolvarea folosește forma din exemplu.

Exemple

`atestat.in`	`atestat.out`	Explicații
`4` `0 0 1 0` `0 0 0 0` `1 0 0 0` `0 0 0 0`	`2 4`	Liniile `2` și `4` sunt formate numai din zerouri
`4` `0 1 1 0` `1 0 0 1` `1 0 0 0` `0 1 0 0`	`nu exista noduri izolate`	Fiecare nod are cel puțin un vecin

Rezolvare

C++

#include <fstream>
using namespace std;

void citire(int a[21][21], int &n) {
    ifstream f("atestat.in");
    f >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) f >> a[i][j];
}

int suma(int v[], int k) {
    int s = 0;
    for (int i = 0; i < k; i++) s += v[i];
    return s;
}

int main() {
    ofstream g("atestat.out");
    int n, a[21][21], gasit = 0;
    citire(a, n);
    for (int i = 0; i < n; i++)
        if (suma(a[i], n) == 0) {        // a[i] = linia i, ca tablou unidimensional
            if (gasit) g << " ";
            g << i + 1;                  // eticheta nodului = indice + 1
            gasit = 1;
        }
    if (!gasit) g << "nu exista noduri izolate";
    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 #596ProgramareEliminarea nodurilor de grad minim și numărul muchiilor rămase (nrElem1 și sumaElem)#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 #054ProgramareSă se schimbe între ele două linii l1 şi l2, date de la tastatură