Sprawdzanie Spojnosci Grafu

Aby sprawdzić spójność grafu (i przy okazji obliczyć wszystkie jego spójne składowe jeśli jest ich więcej niż 1) należy wykonać DFS na grafie pamiętając dla każdego wierzchołka v dodatkowa wartość c[v], która oznacza numer spójnej składowej do której należy wierzchołek v. W tym celu trzymamy sobie globalną zmienna C, która oznacza numer aktualnej spójnej składowej (początkowo 1). W głównej pętli DFS'a za każdym przebiegiem zwiekszamy C o 1 (jeśli graf jest spójny to nigdy nie bedziemy mieli okazji, zeby to zrobic). Przechodząc DFS'em kolejne wierzcholki przypisujemy ich c[] aktualna wartosc C. Jeśli po przejściu całego grafu C==1 to znaczy, że graf jest spójny. Jeśli c[v]==c[u] to znaczy ze wierzchołki v i u należą do tej samej składowej grafu.

Przykładowy kod:

//UWAGA: w przypadku grafów skierowanych ten algorytm sprawdzi czy jest on słabo spójny. Nie uwzględnia przypadku, że istnieje scieżka u~>v, ale v~>u nie istnieje.
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
vector<vector<int> > graf;
deque<int> stos;
vector<int> poprzednik, odwiedzenie, przetworzenie, c;
vector<bool> done;
int N, E, u, v, czas=0, C=0;
const int INF = 1000001;
int directed=0;
 
void ccdfs_visit(int u){
    done[u]=true;
    odwiedzenie[u]=++czas;
    c[u]=C;
    for(vector<int>::iterator it=graf[u].begin(); it!=graf[u].end(); it++){
        int v=*it;
        if(!done[v]){
            poprzednik[v]=u;
            ccdfs_visit(v);
        }
    }
    przetworzenie[u]=++czas;
}
 
void ccdfs(){
    czas=0;
    C=0; //numer aktualnej spojnej skladowej
    if(directed==0){
    for(int i=0; i<N; i++){
        if(!done[i]){
            C++;
            ccdfs_visit(i);
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin>>N>>E>>directed;
    graf.resize(N);
    done.resize(N);
    poprzednik.resize(N, INF);
    odwiedzenie.resize(N, INF);
    przetworzenie.resize(N, INF);
    c.resize(N);
    for(int i=0; i<E; i++){
        cin>>u>>v;
        graf[u-1].push_back(v-1);
        if(directed==0)graf[v-1].push_back(u-1);
    }
    ccdfs();
    if(C==1)cout<<"Graf jest spojny."<<endl;
    else{
        cout<<"Graf nie jest spojny.\n";
        for(int i=0; i<N; i++){
            cout<<"Wierzcholek nr "<<i+1<<" nalezy do spojnej skladowej nr "<<c[i]<<".\n";
        }
        cout<<endl;
    }
    system("pause");
    return 0;
}