Cod sursa(job #358841)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 24 octombrie 2009 18:11:12
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <stdio.h>
#include <vector>
#define Nmax 100005
#define pb push_back
using namespace std;

vector < int > a[Nmax],cc[Nmax],at[Nmax];
vector < int > v;
vector< int >:: iterator it;
vector< int >:: reverse_iterator rit;
int i,j,n,m,x,y,nrc;
int use[Nmax];

void dfs(int x){
vector< int >:: iterator it;
	use[x]=1;
   for(it=a[x].begin(); it!=a[x].end(); it++)
   	if(!use[*it]) dfs(*it);
   v.pb(x);
}

void dfst(int x){
vector< int >:: iterator it;
	use[x]=0;
   cc[nrc].pb(x);
   for(it=at[x].begin(); it!=at[x].end();it++)
   	if(use[*it]) dfst(*it);
}   

int main(){
	freopen("ctc.in","r",stdin);
   freopen("ctc.out","w",stdout);
   scanf("%d%d",&n,&m);
   for(i=1;i<=m;++i){
   	scanf("%d%d",&x,&y);
      a[x].pb(y);
      at[y].pb(x);
   }

   for(i=1;i<=n;++i)
     if(!use[i]) dfs(i);

	for(rit=v.rbegin(); rit!=v.rend(); rit++)
     if(use[*rit]){
       ++nrc;
     	 dfst(*rit);
     }

   printf("%d\n",nrc);
   for(i=1;i<=nrc;++i){
     for(it=cc[i].begin(); it!=cc[i].end(); it++)
       printf("%d ",*it);
     printf("\n");
   }

   fclose(stdin); fclose(stdout);
   return 0;
}