#595 · Subiectul II · Programare

Rădăcina și matricea de adiacență a unui arbore dat prin vectorul de tați

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

Enunț

În fișierul atestat.in, pe prima linie se află un număr natural n (2≤n≤100), numărul de noduri ale unui arbore, iar pe a doua linie n numere naturale, vectorul de tați al arborelui. Nodurile sunt etichetate de la 1 la n.

Se consideră subprogramele:

radacina, cu doi parametri: vectorul de tați v (cel mult 100 de elemente) și n (2≤n≤100). Returnează eticheta nodului rădăcină;
construieste, cu trei parametri: vectorul de tați v, n și matricea pătratică a cu n linii și n coloane. Construiește în memorie și furnizează prin a matricea de adiacență a arborelui.

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

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

c. Scrieți un program care, folosind apeluri utile ale celor două subprograme, citește datele din atestat.in și scrie pe prima linie a lui atestat.out nodul rădăcină, iar pe următoarele n linii câte n valori din {0, 1}, separate prin spațiu, matricea de adiacență a arborelui.

Exemple

`atestat.in`	`atestat.out`	Explicații
`4` `3 4 4 0`	`4` `0 0 1 0` `0 0 0 1` `1 0 0 1` `0 1 1 0`	`v[i]` este tatăl nodului `i`; rădăcina are tatăl `0`, deci este nodul `4`. Muchii: `1–3`, `2–4`, `3–4`

Rezolvare

C++

#include <fstream>
using namespace std;

int radacina(int v[], int n) {
    for (int i = 1; i <= n; i++)
        if (v[i] == 0) return i;         // singurul nod fara tata
    return 0;
}

void construieste(int v[], int n, int a[101][101]) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) a[i][j] = 0;
    for (int i = 1; i <= n; i++)
        if (v[i] != 0) {                 // muchia dintre i si tatal lui
            a[i][v[i]] = 1;
            a[v[i]][i] = 1;              // graf neorientat: matrice simetrica
        }
}

int main() {
    ifstream f("atestat.in");
    ofstream g("atestat.out");
    int n, v[101], a[101][101];
    f >> n;
    for (int i = 1; i <= n; i++) f >> v[i];
    construieste(v, n, a);
    g << radacina(v, n) << "\n";
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) g << a[i][j] << " ";
        g << "\n";
    }
    return 0;
}

Exersează mai departe

Probleme cu aceeași tehnică

#596ProgramareEliminarea nodurilor de grad minim și numărul muchiilor rămase (nrElem1 și sumaElem)#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