Grad interior și exterior într-un graf orientat C++

Într-un graf orientat, relația u→v are un sens. Ea contribuie la gradul exterior al lui u și la gradul interior al lui v. Inversarea capetelor la citire schimbă răspunsul chiar dacă desenul pare să conțină aceleași două vârfuri.

Două numărări pentru fiecare vârf

Gradul interior este numărul arcelor care ajung într-un vârf. Gradul exterior este numărul arcelor care pleacă din el. Pentru arcele 1→2, 1→3 și 3→2, vârful 1 are gradele interior 0, exterior 2; vârful 2 are 2 și 0; vârful 3 are 1 și 1.

Citim 1≤n≤1000 și m arce distincte, fără bucle de la un vârf la el însuși. Vârfurile sunt numerotate 1..n. Pentru fiecare vârf, în această ordine, afișăm gradul interior și gradul exterior. Graful nu este presupus conex și poate avea vârfuri izolate.

Nu memorăm arcele dacă nu le mai folosim

Inițializăm două tablouri de numărări cu zero. Pentru fiecare arc u→v, mărim iesire[u] și intrare[v]. Cerința nu mai folosește relațiile individuale, deci nu este necesară o matrice de adiacență. Această alegere reduce memoria fără să piardă informația cerută.

Tablourile clasice au capacitatea 1001 pentru a folosi indicii 1..n; poziția 0 rămâne nefolosită. Varianta vector construiește n+1 elemente inițializate cu zero. Ambele variante păstrează același format de intrare și ieșire.

Pentru arcele 1→2, 1→3, 3→2, gradele (interior,exterior) sunt (0,2), (2,0), (1,1). Suma fiecărui tip de grad este 3.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
using namespace std;
int main() {
    int n,m; cin >> n >> m;
    int intrare[1001]={},iesire[1001]={};
    for(int i=0;i<m;++i) { int u,v; cin >> u >> v; ++iesire[u]; ++intrare[v]; }
    for(int v=1;v<=n;++v) cout << intrare[v] << ' ' << iesire[v] << '\n';
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
using namespace std;
int main() {
    int n,m; cin >> n >> m;
    vector<int> intrare(n+1),iesire(n+1);
    for(int i=0;i<m;++i) { int u,v; cin >> u >> v; ++iesire[u]; ++intrare[v]; }
    for(int v=1;v<=n;++v) cout << intrare[v] << ' ' << iesire[v] << '\n';
}

O verificare globală a rezultatului

Suma gradelor interioare este m, iar suma gradelor exterioare este tot m. Fiecare arc are exact o destinație și o origine. Nu adunăm cele două tipuri și nu comparăm totalul cu m: suma tuturor celor două numărări este 2m.

Un vârf cu grad interior zero nu are predecesori direcți. Unul cu grad exterior zero nu are succesori direcți. Dacă ambele sunt zero, vârful este izolat. Aceste condiții locale nu demonstrează singure că întregul graf nu are cicluri.

Timpul este O(n+m): citim m arce și afișăm n perechi. Memoria este O(n). Dacă intrarea ar permite arce duplicate dar cerința ar număra numai vecini distincți, această numărare directă ar trebui adaptată; de aceea am precizat contractul.

Exersează

Pentru exemplul cu trei arce, verifică ambele sume egale cu 3. Adaugă un al patrulea vârf izolat și observă linia 0 0. Pentru graful fără arce, toate liniile trebuie să fie 0 0.

Revezi gradele și adiacența, grafurile orientate și numărătorile.

Întrebări frecvente

Care este diferența dintre gradul interior și exterior?

Gradul interior numără arcele care intră într-un vârf, iar gradul exterior arcele care ies din el. Arcul u→v mărește gradul exterior al lui u și gradul interior al lui v.

Cum verific totalurile gradelor într-un graf orientat?

Suma gradelor interioare este egală cu numărul arcelor, la fel și suma gradelor exterioare. Fiecare arc are exact un capăt de plecare și unul de sosire.

Un vârf cu grad interior zero este neapărat izolat?

Nu. Poate avea arce care pleacă spre alte vârfuri. Un vârf izolat are atât grad interior zero, cât și grad exterior zero.