#549 · Subiectul II · Programare

Graf neorientat: nodurile de grad maxim și nodurile izolate (subprogramul suma_x)

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

Enunț

a) Subprogramul suma_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ă suma elementelor de pe linia x. Liniile și coloanele tabloului sunt indexate de la 1. Scrieți la calculator definiția completă a subprogramului.

b) Se consideră un graf neorientat G cu n noduri (n natural, 2 < n < 100), dat prin matricea de adiacență a. Nodurile grafului sunt etichetate cu numere distincte de la 1 la n. Fișierul grade.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 noduri ale grafului, iar pe următoarele linii perechi de numere naturale din intervalul [1, 10²), reprezentând nodurile între care există muchie. Se cere scrierea și executarea la calculator a unui program care citește din grade.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 etichetele nodurilor cu grad maxim, iar pe a doua linie etichetele nodurilor cu grad 0 sau mesajul nu exista, în cazul în care nu există asemenea noduri. Pentru determinarea valorilor cerute se folosesc apeluri utile ale subprogramului suma_x.

Exemple

Date de intrare (`grade.in`)	Date de ieșire (nu neapărat în această ordine)	Explicații
`8` `2 5` `2 6` `2 3` `3 6` `3 7`	`2 3` `1 4 8`	Nodurile 2 și 3 au gradul 3; nodurile 1, 4 și 8 nu au nicio muchie

Rezolvare

C++

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

int a[100][100];

int suma_x(int n, int a[][100], int x) {
    int s = 0;
    for (int j = 1; j <= n; j++) s += a[x][j];
    return s;
}

int main() {
    ifstream f("grade.in");
    int n, x, y;
    f >> n;
    while (f >> x >> y)
        a[x][y] = a[y][x] = 1;          // graf neorientat: matrice simetrica

    int gmax = 0;
    for (int i = 1; i <= n; i++)
        if (suma_x(n, a, i) > gmax) gmax = suma_x(n, a, i);
    for (int i = 1; i <= n; i++)
        if (suma_x(n, a, i) == gmax) cout << i << " ";
    cout << "\n";

    bool izolat = false;
    for (int i = 1; i <= n; i++)
        if (suma_x(n, a, i) == 0) {
            cout << i << " ";
            izolat = true;
        }
    if (!izolat) cout << "nu exista";
    return 0;
}

Exersează mai departe

Probleme cu aceeași tehnică

#553ProgramareGraf orientat: vârfurile cu gradul interior egal cu cel exterior și numărul de arce #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