Cod sursa(job #633241)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 13 noiembrie 2011 12:34:00
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");

const int N=100001;
const int M=200001;

int n,m,nrsol,index[N],low[N],nrindex;
vector <int> edge[N], sol[M];
stack <int> stiva;
bool viz[N];

void citire(){
	int a,b;
	int i;
	in>>n>>m;
	for(i=1;i<=m;i++){
		in>>a>>b;
		edge[a].push_back(b);
	}
}

inline int min(int a,int b){
	return a<b? a: b;
}

void Tarjan(int x){
	int i,y;
	++nrindex;
	viz[x]=true;
	index[x]=nrindex;
	low[x]=nrindex;
	stiva.push(x);
	for(i=0;i<edge[x].size();++i){
		y=edge[x][i];
		if(!viz[y]){
			Tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else{
			low[x]=min(low[x],index[y]);
		}
	}
	if(index[x]==low[x]){
		nrsol++;
		while(stiva.top()!=x){
			sol[nrsol].push_back(stiva.top());
			stiva.pop();
		}
		sol[nrsol].push_back(stiva.top());
		stiva.pop();
	}
}	

void rezolvare(){
	int i;
	for(i=1;i<=n;i++){
		if(!viz[i])
			Tarjan(i);
	}
}

void scriere(){
	int i,j;
	out<<nrsol<<"\n";
	for(i=1;i<=nrsol;++i){
		for(j=0;j<sol[i].size();++j){
			out<<sol[i][j]<<" ";
		}
		out<<"\n";
	}
}

int main(){
	citire();
	rezolvare();
	scriere();
	return 0;
}