Cod sursa(job #1818790)

Utilizator TibiraducanuTiberiu Raducanu Tibiraducanu Data 29 noiembrie 2016 20:22:24
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;

const int N=100005;
int viz[N],viz2[N],cnt;
vector <int> G[N];
vector <int> T[N];
vector <int> Sol[N];
stack <int> st;

void dfs(int x){
    viz[x]=1;
    for(int i=0;i<(int)G[x].size();i++){
        int y=G[x][i];
        if(viz[y]==0) dfs(y);
    }
    st.push(x);
}

void dfs2(int x){
    viz2[x]=1;
    Sol[cnt].push_back(x);
    for(int i=0;i<(int)T[x].size();i++){
        int y=T[x][i];
        if(viz2[y]==0) dfs2(y);
    }
}


int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);

    int n,m,a,b,i,j,x;

    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        T[b].push_back(a);
    }

    for(i=1;i<=n;i++)
        if(viz[i]==0) dfs(i);

    while(!st.empty()){
        x=st.top();
        st.pop();
        if(viz2[x]==1) continue;

        cnt++;
        dfs2(x);
    }

    printf("%d\n",cnt);
    for(i=1;i<=cnt;i++){
        for(j=0;j<(int)Sol[i].size();j++){
            printf("%d ",Sol[i][j]);
        }
        printf("\n");
    }

    return 0;
}