Cod sursa(job #637746)

Utilizator d.andreiDiaconeasa Andrei d.andrei Data 20 noiembrie 2011 16:16:10
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;


#define file_in "ctc.in"
#define file_out "ctc.out"

#define nmax 101000

int N,M;
int a,b,i,ans,j;
int ord[nmax];
int viz[nmax];
vector<int> G[nmax];
vector<int> sol[nmax];

void dfs(int nod){
	
	if (viz[nod])
		return ;
	
	viz[nod]=1;
	vector<int> :: iterator it;
	ord[++ord[0]]=nod;
	
	for (it=G[nod].begin();it!=G[nod].end();++it)
		if (!viz[*it])
			dfs(*it);
}

void dfst(int nod){
	
	if (viz[nod])
		return ;
	
	viz[nod]=1;
	vector<int> :: iterator it;
	sol[ans].push_back(nod);
	
	for (it=G[nod].begin();it!=G[nod].end();++it)
		if (!viz[*it])
			dfst(*it);
}


int main(){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &N, &M);
	while(M--){
		
		scanf("%d %d", &a, &b);
		
		G[a].push_back(b);
	}
	
	for (i=1;i<=N;++i)
		 if (!viz[i])
			 dfs(i);
		 
	memset(viz,0,sizeof(viz));
	ans=0;
	for (i=ord[0];i>=1;--i)
		 if (!viz[i]){
			 ans++;
			 dfst(i);
		 }
		 
	printf("%d\n", ans);
	for (i=1;i<=ans;++i){
		 for (j=0;j<sol[i].size();++j)
			  printf("%d ", sol[i][j]);
		 printf("\n");
	}
		 
	return 0;

}