Cod sursa(job #1538116)

Utilizator ASTELOTudor Enescu ASTELO Data 28 noiembrie 2015 15:42:11
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<cstdio>
#include<vector>
using namespace std;
vector<int> v[100001],v1[100001],r[100001];
int n,m,i,j,k,l,st[100001],cate,vc[100001],cate1,cate2,vc1[100001];
void dfs(int nod)
    {
    vc[nod]=1;
    for(int co=0;co<v[nod].size();co++)
        if(vc[v[nod][co]]==0)
            dfs(v[nod][co]);
    st[++cate]=nod;
    }
 void dfs1(int nod)
    {
    if(vc[nod]==1)
        r[cate1].push_back(nod);
    vc1[nod]=1;
    for(int co=0;co<v1[nod].size();co++)
        if(vc1[v1[nod][co]]==0)
            dfs1(v1[nod][co]);
    }
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);
    v[x].push_back(y);
    v1[y].push_back(x);
    }
for(i=1;i<=n;i++)
    if(vc[i]==0)
        {
        cate=0;
        dfs(i);
        for(j=cate;j>=1;j--)
            if(vc1[st[j]]==0)
                {
                cate1++;
                dfs1(st[j]);
                if(r[cate1].size()==0)
                    cate1--;
                }
        }
printf("%d\n",cate1);
for(i=1;i<=cate1;i++)
    {
    for(j=0;j<r[i].size();j++)
        printf("%d ",r[i][j]);
    printf("\n");
    }
return 0;
}