Cod sursa(job #714117)

Utilizator swift90Ionut Bogdanescu swift90 Data 15 martie 2012 13:48:55
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
int N,M,C,Ind;
int index[100100],lowL[100100];
vector<int> nr[100100],comp[100100];
stack<int> S;
char viz[100100],in_S[100100];
void DF(int x){
	if(viz[x])
		return;
	viz[x]=1;
	++Ind;
	lowL[x]=index[x]=Ind;
	S.push(x);
	in_S[x]=1;
	for(size_t i=0;i<nr[x].size();++i){
		if(!viz[nr[x][i]]){
			DF(nr[x][i]);
			lowL[x]=min(lowL[x],lowL[nr[x][i]]);
		}
		else{
			if(in_S[x])
				lowL[x]=min(lowL[x],index[nr[x][i]]);
		}
	}
	if(index[x]==lowL[x]){
		int nod;
		++C;
		do{
			nod=S.top();
			comp[C].push_back(nod);
			S.pop();
			in_S[nod]=0;
		}while(nod!=x);
	}
}
void afis(){
	printf("%d\n",C);
	for(int i=1;i<=C;++i){
		for(size_t j=0; j<comp[i].size();++j)
			printf("%d ",comp[i][j]);
		printf("\n");
	}
}
int main(){
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	int i,x,y;
	scanf("%d%d",&N,&M);
	for(i=0;i<M;++i){
		scanf("%d%d",&x,&y);
		nr[x].push_back(y);
	}
	for(i=1;i<=N;++i)
		DF(i);
	afis();
	fclose(stdin);
	fclose(stdout);
	return 0;
}