Cod sursa(job #300201)

Utilizator MirageRobert Sandu Mirage Data 7 aprilie 2009 11:59:24
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
#define N 100005
vector < int > v[N];
vector < int > w[N];
bool ins[N];
stack < int > s;
int n,ind[N],sub[N],indice,nrm;
int minim(int x,int y){
	return x<y?x:y;
}
void dfs(int x){
	ind[x] = ++indice;
	s.push(x);
	ins[x] = true;
	sub[x] = indice;
	int nr = v[x].size(),y;
	for(int i=0 ; i<nr ; ++i){
		y=v[x][i];
		if(ind[y] == 0 || ins[y]){
			if(ind[y] == 0)
				dfs(y);
			sub[x] = minim(sub[x],sub[y]);
		}
	}
	if(sub[x] == ind[x]){
		++nrm;
		do{
			y=s.top();
			s.pop();
			w[nrm].push_back(y);
			ins[y] = false;
		}while(y != x);
	}
}
void solve(){
	int nr;
	for(int i=1 ; i<=n ; ++i)
		if(ind[i] == 0)
			dfs(i);
	printf("%d\n",nrm);
	for(int i=1 ; i<=nrm ; ++i){
		nr = w[i].size();
		for(int j=0 ; j<nr ; ++j)
			printf("%d ",w[i][j]);
		printf("\n");
	}
}
int main(){
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	int m,x,y;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;++i){
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
	}
	solve();
	return 0;
}