Cod sursa(job #316784)

Utilizator DraStiKDragos Oprica DraStiK Data 21 mai 2009 09:04:12
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <stdio.h>
#define DIM 100005
struct nod {int x;
            nod *urm;} *lst1[DIM],*lst2[DIM],*rez[DIM];
int viz[DIM],postviz[DIM];
int n,m,nrc,nrt;
void add (nod *&p, int a)
{
    nod *q=new nod;
    q->x=a;
    q->urm=p;
    p=q;
}
void read ()
{
    int i,x,y;
    scanf ("%d%d",&n,&m);
    for (i=1; i<=m; ++i)
    {
        scanf ("%d%d",&x,&y);
        add (lst1[x],y);
        add (lst2[y],x);
    }
}
void df (int start)
{
    nod *p;
    viz[start]=1;
    for (p=lst1[start]; p; p=p->urm)
        if (!viz[p->x])
            df (p->x);
    postviz[++nrc]=start;
}
void dft (int start)
{
    nod *p;
    viz[start]=0;
    add (rez[nrt],start);
    for (p=lst2[start]; p; p=p->urm)
        if (viz[p->x])
            dft (p->x);
}
void solve ()
{
    int i;
    for (i=1; i<=n; ++i)
        if (!viz[i])
            df (i);
    for (i=n; i; --i)
        if (viz[postviz[i]])
        {
	    ++nrt;
            dft (postviz[i]);
        }
}
void print ()
{
    nod *p;
    int i;
    printf ("%d\n",nrt);
    for (i=1; i<=nrt; ++i)
    {
        for (p=rez[i]; p; p=p->urm)
            printf ("%d ",p->x);
        printf ("\n");
    }
}
int main ()
{
    freopen ("ctc.in","r",stdin);
    freopen ("ctc.out","w",stdout);
    read ();
    solve ();
    print ();
    return 0;
}