Cod sursa(job #304102)

Utilizator vanila_CPPIonescu Victor Cristian vanila_CPP Data 10 aprilie 2009 22:25:50
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <algorithm>
#include <vector>
#define FIN "ctc.in"
#define FOUT "ctc.out"
#define PB push_back
#define MAX 100010
using namespace std;
struct ceva{ int index,lowlink;} v[MAX];
vector < int > S;
int index=0;
int N,M;
char def[MAX],inS[MAX];
vector < vector < int > > Comp; 
vector < int > csol;
vector < int > vecini[MAX];



void tarjan(int nod){

	def[nod]=1;
	v[nod].index=index;
	v[nod].lowlink=index;
	++index;
	S.PB(nod);
	inS[nod]++;
	for (int i=1;i<=vecini[nod].size();++i){

		if (def[vecini[nod][i-1]]==0 || inS[vecini[nod][i-1]]){

			if (def[vecini[nod][i-1]]==0) tarjan(vecini[nod][i-1]);
			v[nod].lowlink=min(v[nod].lowlink,v[vecini[nod][i-1]].lowlink);
		}
	}
	if ( v[nod].lowlink==v[nod].index){
		int ok=1;
		csol.clear();
		while(ok){
			int element=S[S.size()-1];
			inS[element]--;
			S.pop_back();
			if (element==nod){ok=0;}
			csol.PB(element);
			
		}
		Comp.PB(csol);
	}
}


int main(void){

	freopen(FIN,"rt",stdin);
	freopen(FOUT,"wt",stdout);

	scanf("%d%d",&N,&M);

	memset(def,0,sizeof(def));
	memset(inS,0,sizeof(inS));

	int x,y;
	for (int i=1;i<=M;++i){
			
		scanf("%d%d",&x,&y);
		vecini[x].PB(y);
	}

	fclose(stdin);

	index=0;

	for (int i=1;i<=N;++i) if (def[i]==0) tarjan(i);

	printf("%d\n",Comp.size());
	for (int i=0;i<Comp.size();++i){
		for (int j=0;j < (Comp[i].size()-1);++j) printf("%d ",Comp[i][j]);
		printf("%d\n",Comp[i][Comp[i].size()-1]);
	}

	fclose(stdout);
	return 0;
}