Cod sursa(job #423678)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 24 martie 2010 10:15:47
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include<stdio.h>
#include<stdlib.h>
#define FIN "ctc.in"
#define FOUT "ctc.out"
#define NMAX 100005
#define MMAX 200004
using namespace std;

struct G
 { int info;
   G *next;
  };
typedef G* Gr;  
Gr Gn[NMAX],Gt[NMAX],REZ[NMAX],adj;
int COLOR[NMAX],n,m,x,y,nr;

void Push(Gr &q , int inf)
{
 Gr p=new G;
 p->info=inf;
 p->next=q;
 q=p;    
}

void DFS(Gr graf[NMAX] , int nod , int Col ,  Gr &rez )
{COLOR[nod]=Col;
 for ( Gr  i = graf [ nod ] ; i ; i = i -> next )
     if(COLOR[i->info]==Col-1)
      DFS(graf,i->info,Col,rez);
 Push(rez,nod);     
 }


int main()
{   freopen(FIN,"r",stdin);
    freopen(FOUT,"w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
     {scanf("%d %d",&x,&y);
      Push(Gn[x],y);
      Push(Gt[y],x);
     }
    for(int i=1;i<=n;i++)
     if(COLOR [ i ]== 0 ) 
       {nr++;
        while(adj) adj=adj->next;
        DFS(Gn,i,1,adj);
        DFS(Gt,i,2,REZ[nr]);
       for(Gr q=adj;q;q=q->next)
        if(COLOR[q->info]==1) COLOR[q->info]=0;
       }
    printf("%d\n",nr);
    for(int i=1;i<=nr;i++)
     {for(Gr q=REZ[i];q;q=q->next)
        printf("%d ",q->info);
      printf("\n");  
     }   
    return 0;
    }