Cod sursa(job #588886)

Utilizator MKLOLDragos Ristache MKLOL Data 9 mai 2011 21:41:33
Problema Arbore partial de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<stdio.h>
#define Nmax 101010
struct nod
{
int val;
nod* next;
} *ga[Nmax],*gt[Nmax],*rez[Nmax];
int N,M,x,y,nr,nrs,coad[Nmax],viz[Nmax];
void add(nod* &a,int q)
{
    //printf("%d\n",q);
    nod* p=new nod;
    p->val=q;
    p->next=a;
    a=p;
}
void df(int x)
{  // printf("%d",x);
    viz[x]=1;
  //  printf("!\n");
    for(nod* a=ga[x];a;a=a->next)
        {//printf("%d ",a->val);
            if(!viz[a->val])
                df(a->val);
        }
    coad[++nr]=x;

}
void df1(int x)
{
    add(rez[nrs],x);
    viz[x]=0;
    for(nod* a=gt[x];a;a=a->next)
        {//printf("%d ",a->val);
            if(viz[a->val])
                df1(a->val);
        }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&N,&M);


    for(int i=1;i<=M;++i)
        {
        scanf("%d%d",&x,&y);
        add(ga[x],y);
        add(gt[y],x);
        }
    for(int i=1;i<=N;++i)
        if(!viz[i])
        {
            df(i);
        }
    for(int i=N;i>=1;--i)
    {
        if(viz[coad[i]])
        ++nrs,df1(coad[i]);

    }
    printf("%d\n",nrs);
    for(int i=1;i<=nrs;++i)
    {
        for(nod* a=rez[i];a;a=a->next)
        {
        printf("%d ",a->val);
        }
        printf("\n");
    }
}