Cod sursa(job #1205584)

Utilizator azkabancont-vechi azkaban Data 7 iulie 2014 13:46:10
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
typedef struct cell {
                     int nod;
                     cell* next;
                     }* list;
                     
list lda[100013],lda_tr[100013],stack,Tare[100013],r;
int n,i,m,a,b,viz[100013],sol(0);

void add(int nod,list &p)
{
 list r=new cell;
 r->nod=nod;
 r->next=p;
 p=r;
}

void dfs(int nod)
{
 viz[nod]=1;
 list r=lda[nod];
 while (r){
           if (!viz[r->nod]) dfs(r->nod);
           r=r->next;
           }
 add(nod,stack);
}

void dfs_tr(int nod)
{
 add(nod,Tare[sol]);
 viz[nod]=1;
 list r=lda_tr[nod];
 while (r){
           if (!viz[r->nod]) dfs_tr(r->nod);
           r=r->next;
           }
}
 
int main()
{ 
 cin>>n>>m; 
 while(cin>>a>>b){
                  add(b,lda[a]);
                  add(a,lda_tr[b]);
                 }
 for (i=1;i<=n;++i)
                if (!viz[i]) dfs(i);
  memset(viz,0,sizeof(viz));
  while (stack){
                if(!viz[stack->nod]) ++sol, dfs_tr(stack->nod);                     
                stack=stack->next;
                }
   cout<<sol<<"\n";
   for (i=1;i<=sol;++i){
                        r=Tare[i];
                        while(r){
                                 cout<<r->nod<<" ";
                                 r=r->next;
                                }
                        cout<<"\n";
                       }            
return 0;
}