De ce contează?
Gândește-te la un autobuz pe traseul lui prin oraș: pleacă de la capăt de linie, trece din stație în stație numai pe străzi cu sens unic — mereu în direcția săgeții — și la final oprește exact la capătul din care a plecat. Nu întâmplător traseul lui se numește chiar „circuit”: un drum care respectă toate sensurile și se închide în punctul de plecare. Dacă o singură stradă ar fi în contrasens, autobuzul n-ar mai putea închide tura.
Ce este
Un circuit este un drum într-un graf orientat în care primul nod
coincide cu ultimul, iar pe parcurs niciun arc nu se repetă. Formal: o secvență
de noduri v0, v1, ..., vk cu v0 = vk, unde fiecare pas vi → vi+1 este un
arc existent, parcurs în sensul lui.
Imaginea mentală: săgeți înlănțuite cap la coadă, iar ultima săgeată se lipește exact de coada primeia. Circuitul este pentru grafurile orientate exact ce este ciclul pentru cele neorientate:
- pe un graf neorientat, un drum închis se numește ciclu — muchiile nu au sens;
- pe un graf orientat, un drum închis se numește circuit — arcele au sens și trebuie parcurse toate „în direcția săgeții”.
Două diferențe esențiale față de ciclu. Prima e sensul: aceleași noduri
legate „în cerc” formează un ciclu dacă muchiile nu au direcție, dar formează un
circuit doar dacă toate săgețile se înlănțuie în același sens de jur
împrejur. A doua e lungimea minimă: un circuit poate avea lungimea 2 —
arcele x → y și y → x sunt arce diferite (au sensuri opuse), deci drumul
x → y → x nu repetă niciun arc. Pe neorientat așa ceva e imposibil:
întoarcerea ar refolosi aceeași muchie, deci un ciclu are cel puțin lungimea 3.
Cum arată
Pornește animația de mai jos și urmărește două lucruri: cum fiecare săgeată este
parcursă în sensul ei (niciodată invers) și cum ultimul arc te aduce înapoi
exact în nodul de plecare. Drumul 0 → 1 → 2 → 3 → 4 → 0 se închide — acesta e
un circuit.
Folosește ← și → ca să pășești arc cu arc, sau Redă pentru animație. La fiecare pas, verifică direcția săgeții pe care tocmai ai parcurs-o: dacă ai merge vreodată contra săgeții, n-ar mai fi drum orientat — deci nici circuit.
Pe un exemplu mai mic: fie trei noduri legate prin arcele 1 → 2, 2 → 3 și
3 → 1. Plecând din 1 și mergând mereu în sensul săgeților, te întorci în 1:
1 | 2 | 3 | 1 |
0 | 1 | 2 | 3 |
start | revine-aici |
Dacă unul dintre arce ar fi în sens invers — de exemplu 1 → 3 în loc de
3 → 1 — n-ai mai putea reveni în 1 urmând sensurile, deci circuitul dispare.
Pe un graf neorientat, însă, aceleași trei legături ar forma în continuare
un ciclu: fără sensuri, nu are ce să se „rupă”. Iar la capătul celălalt al
spectrului, cel mai scurt circuit posibil are doar două arce: 7 → 9 urmat de
9 → 7 te aduce înapoi în 7 fără să repeți vreun arc.
Vrei să verifici dacă un graf orientat conține un circuit. Prima idee: refolosești
detectarea de ciclu de la grafuri neorientate — un vector vizitat, faci DFS și,
dacă dai peste un nod deja vizitat (altul decât părintele), anunți circuit.
Ia arcele 1 → 2, 2 → 3, 1 → 3. DFS din 1 merge 1 → 2 → 3 și termină.
Înapoi în 1, arcul 1 → 3 duce spre un nod deja vizitat, deci metoda naivă
strigă „circuit!”. Dar nu există niciunul: din 3 nu pleacă niciun arc, drumul
nu se poate închide. Pe orientat, „vizitat” nu mai înseamnă „pe drumul curent”.
Trebuie să deosebești două feluri de „vizitat”: nodurile aflate încă pe drumul curent (pe stiva de recursie) și nodurile complet terminate. Doar un arc spre prima categorie închide un circuit. De aici cele trei culori: alb / gri / negru.
DFS cu trei stări: la intrare colorezi nodul gri, la ieșire negru. Arc
spre un nod gri → circuit (ai închis drumul curent). Arc spre un nod negru →
nimic, subarborele acela s-a terminat. Total O(n + m).
Implementare C++
Traducerea directă a ideii de mai sus — fiecare nod primește una dintre cele trei stări:
- alb = neatins încă;
- gri = în curs de explorare (este pe drumul curent, pe stiva de recursie);
- negru = complet explorat (toți descendenții lui au fost terminați).
#include <iostream>
#include <vector>
using namespace std;
const int ALB = 0, GRI = 1, NEGRU = 2;
int n; // numar de noduri
vector<int> adj[1005]; // liste de adiacenta (arce orientate)
int culoare[1005]; // starea fiecarui nod: ALB / GRI / NEGRU
bool areCircuit(int nod) {
culoare[nod] = GRI; // intram in nod: il punem pe drumul curent
for (int vecin : adj[nod]) {
if (culoare[vecin] == GRI) {
return true; // arc spre un stramos gri => circuit
}
if (culoare[vecin] == ALB && areCircuit(vecin)) {
return true; // circuit gasit mai jos in recursie
}
// vecin NEGRU: subarbore deja terminat, nu inchide niciun drum curent
}
culoare[nod] = NEGRU; // am terminat nodul: iese de pe drumul curent
return false;
}
int main() {
int m; // numar de arce
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b; // arc orientat de la a la b
adj[a].push_back(b);
}
bool gasit = false;
for (int i = 1; i <= n; i++) {
if (culoare[i] == ALB && areCircuit(i)) {
gasit = true;
break;
}
}
cout << (gasit ? "DA" : "NU") << "\n"; // DA daca exista circuit
return 0;
}Fiecare nod și fiecare arc sunt parcurse o singură dată, deci complexitatea este
O(n + m), unde n e numărul de noduri și m numărul de arce.
Două capcane surori. Prima, la definiție: aplici regula ciclului pe graf
orientat (sau invers). Pe orientat, x → y plus y → x este circuit — de
lungime 2 — deși pe neorientat aceleași noduri nu ar forma niciun ciclu; iar un
„cerc” de noduri e circuit doar dacă toate săgețile merg în același sens.
A doua, la detectare: folosești doar două stări (vizitat / nevizitat) ca la neorientat. A ajunge la un nod deja vizitat nu înseamnă automat circuit — contează dacă e încă pe drumul curent. Un nod negru (subarbore complet explorat) atins din nou nu formează circuit; doar un nod gri (strămoș pe drumul curent) îl închide. Confunzi gri cu negru și fie raportezi circuite inexistente, fie le ratezi.