Cod sursa(job #526661)

Utilizator DraStiKDragos Oprica DraStiK Data 29 ianuarie 2011 09:28:59
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <algorithm>
#include <vector>
using namespace std;

#define pb push_back
#define DIM 100005

vector <int> g[DIM],gt[DIM],ct[DIM];
int postviz[DIM];
int n,m,nrc,ctc;
bool viz[DIM];

void read ()
{
    int i,x,y;

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

void df (int nod)
{
    vector <int> :: iterator it;

    viz[nod]=1;
    for (it=g[nod].begin (); it!=g[nod].end (); ++it)
        if (!viz[*it])
            df (*it);
    postviz[++nrc]=nod;
}

void dft (int nod)
{
    vector <int> :: iterator it;

    viz[nod]=0;
    ct[ctc].pb (nod);
    for (it=gt[nod].begin (); it!=gt[nod].end (); ++it)
        if (viz[*it])
            dft (*it);
}

void solve ()
{
    int i;

    for (i=1; i<=n; ++i)
        if (!viz[i])
            df (i);
    for (i=n; i>=1; --i)
        if (viz[postviz[i]])
        {
            ++ctc;
            dft (postviz[i]);
        }
}

void print ()
{
    vector <int> :: iterator it;
    int i;

    printf ("%d\n",ctc);
    for (i=1; i<=ctc; ++i)
    {
        for (it=ct[i].begin (); it!=ct[i].end (); ++it)
            printf ("%d ",*it);
        printf ("\n");
    }
}

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

    read ();
    solve ();
    print ();

    return 0;
}