Cod sursa(job #270550)

Utilizator igsifvevc avb igsi Data 4 martie 2009 09:53:48
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<fstream.h>

#define xn 100001
#define xm 200001

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int u[xn],n,m,st[xn],nr;
struct lista {int nod; lista *urm; } *g[xn],*gt[xn];

void df1(int nod);
void df2(int nod);

int main()
{
    int i,x,y;
    lista *p;
    
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
      fin>>x>>y;
      p=new lista;
      p->nod=y;      p->urm=g[x];      g[x]=p;
      p=new lista;
      p->nod=x;      p->urm=gt[y];      gt[y]=p;
    }
    
    for(i=1;i<=n;i++)
      if(!u[i])
        df1(i);
    
    memset(u,0,sizeof(u));
    
    for(i=n;i>0;i--)
      if(!u[st[i]])
        nr++,df2(st[i]);
    
    fout<<nr<<'\n';
    
    for(x=1;x<=nr;x++)
    {   
       for(i=1;i<=n;i++)
         if(u[i]==x)
           fout<<i<<' ';
       fout<<'\n';
    }
    
    fout.close();
    return 0;
}

void df2(int nod)
{
     lista *p;
     u[nod]=nr;
     for(p=gt[nod];p;p=p->urm)
       if(!u[p->nod])
         df2(p->nod);
}

void df1(int nod)
{
     lista *p;
     u[nod]=1;
     for(p=g[nod];p;p=p->urm)
        if(!u[p->nod])
          df1(p->nod);
     
     st[++st[0]]=nod;
}