Cod sursa(job #476716)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 12 august 2010 11:18:45
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<cstdio>
#include<bitset>
#include<vector>

using namespace std;

int i,n,m,sorta[100100],nr,j;
vector<int> a[100100];
vector<int> at[100100];
vector< vector<int> > rez;
bitset<100100> fol;

void dfs(int i)
{
    fol[i]=1;
    for(int j=0;j<a[i].size();++j)
    if(!fol[a[i][j]]) dfs(a[i][j]);

    sorta[++nr]=i;
}

void dfs2(int i)
{
    fol[i]=0;
    rez[rez.size()-1].push_back(i);
    for(int j=0;j<at[i].size();++j)
    if(fol[at[i][j]]) dfs2(at[i][j]);
}

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

    scanf("%d%d",&n,&m);

    for(i=1;i<=m;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        a[x].push_back(y);
        at[y].push_back(x);
    }

    for(i=1;i<=n;++i)
    if(!fol[i]) dfs(i);

    vector<int> aux;
    for(i=n;i>0;--i)
    if(fol[ sorta[i] ])
    {
        rez.push_back(aux);
        dfs2(sorta[i]);
    }

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

    fclose(stdin);
    fclose(stdout);
    return 0;
}