Cod sursa(job #484819)

Utilizator MarioYCMario Ynocente Castro MarioYC Data 15 septembrie 2010 22:34:43
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX_V 100000

vector<int> L[MAX_V];
int V,dfsPos,dfsNum[MAX_V],lowlink[MAX_V],num_scc;
bool in_stack[MAX_V];
vector<int> C[MAX_V];
stack<int> S;

void tarjan(int v){
    dfsNum[v] = lowlink[v] = dfsPos;
    ++dfsPos;
    
    S.push(v); in_stack[v] = true;
    
    for(int i = L[v].size()-1;i>=0;--i){
        int w = L[v][i];
        if(dfsNum[w]==-1){
            tarjan(w);
            lowlink[v] = min(lowlink[v],lowlink[w]);
        }else if(in_stack[w]) lowlink[v] = min(lowlink[v], lowlink[w]);
    }
    
    if(dfsNum[v]==lowlink[v]){
        vector<int> com;
        int aux;
        
        do{
            aux = S.top(); S.pop();
            com.push_back(aux);
            in_stack[aux] = false;
        }while(aux!=v);
        
        C[num_scc] = com;
        ++num_scc;
    }
}

void build_scc(){
    memset(dfsNum,-1,sizeof(dfsNum));
    memset(in_stack,false,sizeof(in_stack));
    dfsPos = num_scc = 0;
    
    for(int i = 0;i<V;++i)
        if(dfsNum[i]==-1)
            tarjan(i);
}

int main(){
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);    
    
	int M,u,v;
    scanf("%d %d",&V,&M);
    
    while(M--){
        scanf("%d %d",&u,&v);
        L[u-1].push_back(v-1);
    }
    
    build_scc();
    
    printf("%d\n",num_scc);
    
    for(int i = 0;i<num_scc;++i){
        for(int j = C[i].size()-1;j>=0;--j)
            printf("%d ",1+C[i][j]);
        printf("\n");
    }

    return 0;
}