Cod sursa(job #2443368)

Utilizator Leonard123Mirt Leonard Leonard123 Data 27 iulie 2019 16:18:17
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
#define maxn 100005
vector<int>ans[maxn],V[maxn],Stack;
int onstack[maxn],g[maxn],index[maxn],lowlink[maxn],Index=1,N,M,number,x;

void read(){
    cin>>N>>M;
    int x,y;
    for(int i=1; i<=M; i++){
        cin>>x>>y;
        V[x].push_back(y);
        g[x]++;
    }
}

void tarjan(int nod){
    index[nod]=Index;
    lowlink[nod]=Index;
    Index++;
    Stack.push_back(nod);
    onstack[nod]=1;
    for(int i=g[nod]-1; i>=0; i--){
        if(index[V[nod][i]]==0){
            tarjan(V[nod][i]);
            lowlink[nod]=min(lowlink[V[nod][i]],lowlink[nod]);
        } else if(onstack[V[nod][i]])
            lowlink[nod]=min(lowlink[nod],lowlink[V[nod][i]]);
    }

    if(lowlink[nod]==index[nod]){
        number++;
        do{
            x=Stack.back();
            ans[number].push_back(x);
            onstack[x]=0;
            Stack.pop_back();
        }while(nod!=x);
    }

}

void solve(){
    for(int i=1; i<=N; i++)
        if(index[i]==0)
            tarjan(i);
    cout<<number<<'\n';
    for(int i=1; i<=number; i++){
        while(!ans[i].empty()){
            cout<<ans[i].back()<<' ';
            ans[i].pop_back();
        }
        cout<<'\n';
    }
}

int main(){
    read();
    solve();
}