Cod sursa(job #369235)

Utilizator cristikIvan Cristian cristik Data 27 noiembrie 2009 16:53:04
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <stdio.h>
#define max 100005
struct lista
{
    int nod;
    lista *urm;
};
lista *g[max],*gt[max],*r[max],*p;
int postordine[max],i,j,n,m,nr,nrcp;
char s[max];
void dfs(int nod)
{
    lista *p;
    s[nod]=1;
    for(p=g[nod]; p!=NULL; p=p->urm)
     if(!s[p->nod]) dfs(p->nod);
    postordine[++nr]=nod;
}
void dfst(int nod)
{
    lista *p;
    p=new lista; p->nod=nod; p->urm=r[nrcp]; r[nrcp]=p;
    s[nod]=0;
    for(p=gt[nod]; p!=NULL; p=p->urm)
     if(s[p->nod]) dfst(p->nod);
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(; m>0 ;m--)
    {
        scanf("%d%d",&i,&j);
        p=new lista;
        p->nod=j;
        p->urm=g[i];
        g[i]=p;
        p=new lista;
        p->nod=i;
        p->urm=gt[j];
        gt[j]=p;
    }
    for(i=1; i<=n; i++)
     if(!s[i]) dfs(i);
    for(i=n; i>0; i--)
     if(s[postordine[i]])
     {
         ++nrcp;
         dfst(postordine[i]);
     }
    printf("%d\n",nrcp);
    for(i=1; i<=nrcp; i++)
    {
        p=r[i];
        while(p)
        {
            printf("%d ",p->nod);
            p=p->urm;
        }
        printf("\n");
    }
    return 0;
}