#553 · Subiectul II · Programare

Graf orientat: vârfurile cu gradul interior egal cu cel exterior și numărul de arce

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

Enunț

a) Subprogramul linie_x are trei parametri, prin care primește: n, un număr natural din intervalul [1, 100); a, un tablou bidimensional cu n×n valori naturale; x, un număr natural din intervalul [1, n]. Subprogramul returnează numărul elementelor nenule de pe linia x. Liniile și coloanele tabloului sunt indexate de la 1. Scrieți la calculator definiția completă a subprogramului.

b) Subprogramul coloana_x are aceiași trei parametri și returnează numărul elementelor nenule de pe coloana x. Scrieți la calculator definiția completă a subprogramului.

c) Se consideră un graf orientat G cu n vârfuri (n natural, 2 < n < 100), dat prin matricea de adiacență a. Vârfurile grafului sunt etichetate cu numere distincte de la 1 la n. Fișierul graf.in conține mai multe linii. Pe prima linie a fișierului este scris un număr natural nenul n (n < 100), ce reprezintă numărul de vârfuri ale grafului, iar pe următoarele linii perechi de numere naturale din intervalul [1, 10²), reprezentând vârfurile între care există arc. Se cere scrierea și executarea la calculator a unui program care citește din fișierul graf.in numărul n și perechile de numere, construiește în memorie matricea de adiacență a grafului și afișează pe prima linie a ecranului, separate prin câte un spațiu, vârfurile care au gradul interior egal cu gradul exterior sau mesajul nu exista, pentru cazul în care nu există vârfuri cu această proprietate, iar pe a doua linie a ecranului, numărul de arce ale grafului. Pentru afișarea valorilor cerute se folosesc apeluri utile ale subprogramelor linie_x și coloana_x.

Exemple

Date de intrare (`graf.in`)	Date de ieșire (nu neapărat în această ordine)	Explicații
`6` `1 2` `3 1` `3 2` `4 3` `5 3` `6 5`	`1 3 5` `6`	Vârful 1: un arc intră, unul iese; 3: câte 2; 5: câte 1. Graful are 6 arce

Rezolvare

C++

#include <fstream>
#include <iostream>
using namespace std;

int a[100][100];

int linie_x(int n, int a[][100], int x) {     // grad exterior
    int c = 0;
    for (int j = 1; j <= n; j++)
        if (a[x][j] != 0) c++;
    return c;
}

int coloana_x(int n, int a[][100], int x) {   // grad interior
    int c = 0;
    for (int i = 1; i <= n; i++)
        if (a[i][x] != 0) c++;
    return c;
}

int main() {
    ifstream f("graf.in");
    int n, x, y;
    f >> n;
    while (f >> x >> y) a[x][y] = 1;          // arc x -> y, un singur sens

    bool gasit = false;
    int arce = 0;
    for (int i = 1; i <= n; i++) {
        if (linie_x(n, a, i) == coloana_x(n, a, i)) {
            cout << i << " ";
            gasit = true;
        }
        arce += linie_x(n, a, i);             // fiecare arc pleaca dintr-un varf
    }
    if (!gasit) cout << "nu exista";
    cout << "\n" << arce;
    return 0;
}

Exersează mai departe

Probleme cu aceeași tehnică

#549ProgramareGraf neorientat: nodurile de grad maxim și nodurile izolate (subprogramul suma_x)#560ProgramareArbore dat prin vectorul de tați: rădăcina, nodurile cu cei mai mulți fii și frunzele (subprogramul pozitie)#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)#597ProgramareNodurile izolate dintr-un graf dat prin matricea de adiacență (citire și suma)#041ProgramareSă se numere apariţiile unui cuvânt dat, citit de la tastatură, în text