Cod sursa(job #828491)

Utilizator stef1995mmarcu stefan ovidiu stef1995m Data 3 decembrie 2012 20:40:53
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int maxx=100008;
int n,m,i,viz[maxx],a,b,line,j;
vector < int > x[maxx],xt[maxx],sol[maxx];
void read()
{
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        x[a].push_back(b);
        xt[b].push_back(a);
    }
}
void df(int nod,int value)
{
    viz[nod]=1;
    for(int i=0;i<x[nod].size();i++)
        if(viz[x[nod][i]]==false)
            df(x[nod][i],value);
}
void df2(int nod,int value)
{
    viz[nod]=2;
    for(int i=0;i<xt[nod].size();i++)
        if(viz[xt[nod][i]]==1)
            df2(xt[nod][i],value);
    sol[line].push_back(nod);
}
void write()
{
    printf("%d\n",line);
    for(i=1;i<=line;i++,printf("\n"))
        for(j=0;j<sol[i].size();j++)
            printf("%d ",sol[i][j]);
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    read();
    for(i=1;i<=n;i++)
    {
        if(viz[i]==false)
        {
            line++;
            df(i,1);
            df2(i,2);
            for(j=1;j<=n;j++)
                if(viz[j]==1)
                    viz[j]=0;
        }
    }
    write();
    return 0;
}