Cod sursa(job #939980)

Utilizator dariusdariusMarian Darius dariusdarius Data 15 aprilie 2013 12:12:00
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
vector<int> ctc,v[100005],vt[100005],sol[100005];
stack<int> st;
vector<bool> viz;int cnt;
void dfs_plus(int u)
{
    if(!viz[u])
    {
        viz[u]=true;
        for_each(v[u].begin(),v[u].end(),dfs_plus);
        st.push(u);
    }
}
void dfs_minus(int u)
{
    if(ctc[u]==-1)
    {
        ctc[u]=cnt;
        for_each(vt[u].begin(),vt[u].end(),dfs_minus);
    }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    int n,m,x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        x--;y--;
        v[x].push_back(y);
        vt[y].push_back(x);
    }
    viz.assign(n,false);
    for(int i=0;i<n;i++)
        dfs_plus(i);
    ctc.assign(n,-1);
    while(!st.empty())
    {
        if(ctc[st.top()]==-1)
            dfs_minus(st.top()),
            cnt++;
        st.pop();
    }
    for(int i=0;i<n;i++)
        sol[ctc[i]].push_back(i);
    printf("%d\n",cnt);
    for(int i=0;i<cnt;i++,printf("\n"))
        for(vector<int>::iterator it=sol[i].begin();it!=sol[i].end();++it,printf(" "))
            printf("%d",*it+1);
    return 0;
}