Cod sursa(job #412240)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 5 martie 2010 14:06:15
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>
#include <vector>

using namespace std;

const int Lg = 100010;
vector <int > V[Lg],Vt[Lg],Rez[Lg];
int viz[Lg];
int sir[Lg];
int n,m,a,b,nr,nr_rez;

void citire()
{
    scanf ("%d %d",&n,&m);
    for (int i=0;i<m;i++)
    {
        scanf ("%d %d",&a,&b);
        V[a].push_back(b);
        Vt[b].push_back(a);
    }
}

void df(int nod)
{
    viz[nod]=1;
    for (int i=0;i<V[nod].size();i++)
        if (!viz[V[nod][i]])
            df(V[nod][i]);
    sir[nr++]=nod;
}

void df2(int nod)
{
    viz[nod]=0;
    Rez[nr_rez].push_back(nod);
    for (int i=0;i<Vt[nod].size();i++)
        if (viz[Vt[nod][i]])
            df2(Vt[nod][i]);
}

void solve()
{
    for (int i=1;i<=n;i++)
        if (!viz[i])
            df(i);

    for (int i=n-1;i>=0;i--)
        if (viz[sir[i]])
        {
            df2(sir[i]);
            nr_rez++;
        }

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

int main ()
{
    freopen ("ctc.in","r",stdin);
    freopen ("ctc.out","w",stdout);
    citire();
    solve();
    return 0;
}