Cod sursa(job #674069)

Utilizator Eugen01Vasilescu Eugen Eugen01 Data 5 februarie 2012 14:46:07
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<stdio.h>
#include<vector>
#include<string.h>
#define pb push_back
#define Nmax 100009

using namespace std;

int n,m,i,x,y,nr,ok[Nmax];
vector<int> a[Nmax],b[Nmax],sol[Nmax],Q;

void DF1(int nod)
{
    ok[nod]=1;
    for (vector<int>::iterator it=a[nod].begin();it!=a[nod].end();it++)
        if (!ok[*it]) DF1(*it);
    Q.pb(nod);
}

void DF2(int nod)
{
    ok[nod]=1;
    sol[nr].pb(nod);
    for (vector<int>::iterator it=b[nod].begin();it!=b[nod].end();it++)
        if (!ok[*it]) DF2(*it);
}

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

    scanf("%d%d",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        a[x].pb(y);
        b[y].pb(x);

    }
    for (i=1;i<=n;i++)
        if (!ok[i]) DF1(i);
    memset(ok,0,sizeof(ok));

    for (i=Q.size()-1;i>=0;i--)
        if (!ok[Q[i]])
        {
            nr++;
            DF2(Q[i]);
        }
    printf("%d\n",nr);
    for (i=1;i<=nr;i++)
    {
        for (vector<int>::iterator it=sol[i].begin();it!=sol[i].end();it++)
            printf("%d ",*it);
        printf("\n");
    }
}