Cod sursa(job #1082331)

Utilizator TodeaDariustodea darius TodeaDarius Data 14 ianuarie 2014 15:03:40
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<cstdio>
#include<vector>
using namespace std;
vector<int>a[100005];
vector<int>b[100005];
vector<int>c[100005];
int n,m,viz[100005],stv[100005],k,sol;
void citire()
{
    int x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        a[x].push_back(y);
        b[y].push_back(x);
    }
}
void dfs(int x)
{
    viz[x]=1;
    for(int i=0;i<a[x].size();i++)
    {
        if(viz[a[x][i]]==0)
        {
            dfs(a[x][i]);
        }
    }
    stv[++k]=x;
}
void dfs1(int x)
{
    viz[x]=0;
    c[sol].push_back(x);
    for(int i=0;i<b[x].size();i++)
    {
        if(viz[b[x][i]]==1)
        {
            dfs1(b[x][i]);
        }
    }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);

    citire();k=0;sol=1;
    for(int i=1;i<=n;i++)
        if(viz[i]==0)
            dfs(i);
    for(int i=k;i>=1;i--)
        if(viz[stv[i]]==1)
        {
            dfs1(stv[i]);
            sol++;
        }
    sol--;
    printf("%d\n",sol);
    for(int i=1;i<=sol;i++)
    {
        for(int j=0;j<c[i].size();j++)
            printf("%d ",c[i][j]);
        printf("\n");
    }
}