Cod sursa(job #782144)

Utilizator ion824Ion Ureche ion824 Data 25 august 2012 23:44:37
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include<fstream>
using namespace std;
typedef struct lnod{
        int vf;
        struct lnod *next;
        }*Nod;
const int NM=100003;
Nod G[NM],T[NM],S[NM];
int e[NM+NM],lev,ne;
bool viz[NM];

void add(Nod &q,int x){
     Nod p=new lnod;
     p->vf=x;
     p->next=q;
     q=p;
     }
     
void dfs1(int nod){
     viz[nod]=1;
     e[++ne]=nod;
     for(Nod p=G[nod];p;p=p->next)
       if(!viz[p->vf])
         {
          dfs1(p->vf);
          e[++ne]=nod;             
         }     
     }     
     
void dfs2(int nod){
     add(S[lev],nod);
     viz[nod]=0;
     for(Nod p=T[nod];p;p=p->next)
       if(viz[p->vf])
       {
         viz[p->vf]=0;
         dfs2(p->vf);           
       }
     }
     
int main(void){
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    int i,N,M,x,y;
    fin>>N>>M;
    for(i=1;i<=M;++i)
    {
     fin>>x>>y;
     add(G[x],y);
     add(T[y],x);                 
    }
    
    for(i=1;i<=N;++i)
      if(!viz[i])
        dfs1(i);
    
    for(i=ne;i>0;--i)
      if(viz[e[i]])
       {
        ++lev;
        dfs2(e[i]);            
       }
   
   fout<<lev<<'\n';     
   for(i=1;i<=lev;++i){
     for(Nod p=S[i];p;p=p->next)
       fout<<p->vf<<' ';
       fout<<'\n';
       }
         
 return 0;   
}