Numărul drumurilor într-un graf orientat aciclic C++

Un graf orientat aciclic are arce cu sens și nu conține niciun ciclu orientat. Este numit și DAG, de la Directed Acyclic Graph. Într-un astfel de graf putem ordona vârfurile astfel încât fiecare arc să meargă de la un vârf mai devreme la unul mai târziu. Aceasta este o ordine topologică.

Câte drumuri ajung într-un vârf

Dacă știm numărul drumurilor de la sursa s la fiecare predecesor al lui v, le adunăm pentru a obține numărul drumurilor până la v. Fiecare drum care ajunge în v se încheie printr-un anumit arc u→v, deci grupurile după ultimul arc nu se suprapun.

Citim 1≤n≤100, m arce distincte fără bucle, apoi sursa s și ținta t în aceeași primă linie. Formatul este n m s t, urmat de arce. Afișăm numărul drumurilor de la s la t modulo 1000000007, adică restul împărțirii la acest număr. Dacă graful are un ciclu, afișăm GRAF CU CICLU, deoarece metoda nu se aplică.

Pregătim ordinea prin grade interioare

Gradul interior este numărul arcelor care intră într-un vârf. Punem în coadă toate vârfurile cu grad interior zero. La extragerea lui u, propagăm numărul drumurilor sale spre fiecare vecin v și micșorăm gradul interior rămas al lui v. Când acesta devine zero, toți predecesorii au fost procesați și v poate intra în coadă.

Pornim cu cai[s]=1 pentru drumul de lungime zero de la s la el însuși. Celelalte valori sunt zero. Astfel, dacă s=t și graful este aciclic, răspunsul este 1, convenție declarată explicit.

În graful 1→2,1→3,2→4,3→4, există două drumuri de la 1 la 4: prin 2 și prin 3. Numărul pentru 4 este 1+1=2.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
#include <queue>
using namespace std;
int main() {
    int n,m,s,t; cin >> n >> m >> s >> t;
    int a[101][101]={},grad[101]={}; long long cai[101]={};
    for(int i=0;i<m;++i) { int u,v; cin >> u >> v; a[u][v]=1; ++grad[v]; }
    queue<int> q; for(int u=1;u<=n;++u) if(grad[u]==0) q.push(u);
    cai[s]=1; int procesate=0; const long long MOD=1000000007;
    while(!q.empty()) {
        int u=q.front(); q.pop(); ++procesate;
        for(int v=1;v<=n;++v) if(a[u][v]) {
            cai[v]=(cai[v]+cai[u])%MOD;
            if(--grad[v]==0) q.push(v);
        }
    }
    if(procesate!=n) cout << "GRAF CU CICLU\n"; else cout << cai[t] << '\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>
#include <queue>
using namespace std;
int main() {
    int n,m,s,t; cin >> n >> m >> s >> t;
    vector<vector<int>> a(n+1,vector<int>(n+1)); vector<int> grad(n+1); vector<long long> cai(n+1);
    for(int i=0;i<m;++i) { int u,v; cin >> u >> v; a[u][v]=1; ++grad[v]; }
    queue<int> q; for(int u=1;u<=n;++u) if(grad[u]==0) q.push(u);
    cai[s]=1; int procesate=0; const long long MOD=1000000007;
    while(!q.empty()) {
        int u=q.front(); q.pop(); ++procesate;
        for(int v=1;v<=n;++v) if(a[u][v]) {
            cai[v]=(cai[v]+cai[u])%MOD;
            if(--grad[v]==0) q.push(v);
        }
    }
    if(procesate!=n) cout << "GRAF CU CICLU\n"; else cout << cai[t] << '\n';
}

Un diamant are două drumuri

Pentru arcele 1→2, 1→3, 2→4 și 3→4, din 1 în 4 există două drumuri. Valoarea lui cai[4] primește contribuția 1 de la 2 și contribuția 1 de la 3. Nu numărăm doar vecinii sursei și nu marcăm ținta „rezolvată” la prima contribuție.

Dacă procesăm mai puțin de n vârfuri, unele grade nu au putut ajunge la zero din cauza unui ciclu. Nu folosim un rezultat parțial ca răspuns pentru întregul graf. O componentă ciclică separată este și ea raportată, conform contractului.

Matricea de adiacență determină timp O(n²+m) și memorie O(n²). Reducerea modulo după fiecare adunare păstrează numerele mici; în long long, suma a două resturi din intervalul folosit este sigură.

Exersează

Diamantul descris produce 2. O țintă inaccesibilă produce 0. Pentru un singur vârf, s=t=1, rezultatul este 1. Un ciclu 1→2→1 trebuie raportat ca invalid pentru această metodă.

Revezi sortarea topologică, programarea dinamică și calculele modulo.

Întrebări frecvente

Ce înseamnă DAG?

DAG vine de la Directed Acyclic Graph, adică graf orientat aciclic. Nu conține cicluri orientate și admite o ordine topologică în care fiecare arc merge înainte.

Cum număr drumurile într-un graf orientat aciclic?

Inițializează sursa cu un drum de lungime zero, apoi procesează vârfurile în ordine topologică. Pentru fiecare arc u→v, contribuția drumurilor până la u se adaugă la numărul drumurilor până la v.

De ce nu ajunge ordinea numerică a vârfurilor?

Etichetele nu garantează ordinea dependențelor. Un arc poate merge de la un număr mare la unul mic. Folosește o ordine topologică, exceptând situația în care enunțul garantează deja una.