Cod sursa(job #749709)

Utilizator BitOneSAlexandru BitOne Data 18 mai 2012 11:23:28
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <stack>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>

using namespace std;
const int N_MAX=100011;

int idx, ctcSize;
bool was[N_MAX], isInStack[N_MAX];
int dfsIDX[N_MAX], lowIDX[N_MAX];

stack<int> S;
vector<int> G[N_MAX], CTC[N_MAX];
vector<int>::const_iterator it, iend;

inline void DFS(int x)
{
	S.push(x);
	was[x]=true;
	isInStack[x]=true;
	lowIDX[x]=dfsIDX[x]=++idx;
	vector<int>::const_iterator it=G[x].begin(), iend=G[x].end();
	
	for(; it < iend; ++it)
	{
		if(false == was[*it])
		{
			DFS(*it);
			if(lowIDX[*it] < lowIDX[x])
				lowIDX[x]=lowIDX[*it];
		}
		else if(true == isInStack[*it] && lowIDX[*it] < lowIDX[x])
				lowIDX[x]=lowIDX[*it];
	}
	if(lowIDX[x] == dfsIDX[x])
	{
		int y;
		do {
			   y=S.top(); S.pop();
			   isInStack[y]=false;
			   CTC[ctcSize].push_back(y);
		   }while(y != x);
		 ++ctcSize;
	}
}
int main()
{
	int N, M, x, y;
	ifstream in("ctc.in");
	ofstream out("ctc.out");
	
	for(in>>N>>M; M; --M)
	{
		in>>x>>y;
		G[x].push_back(y);
	}
	for(x=1; x <= N; ++x)
		if(false == was[x])
			DFS(x);
	out<<ctcSize<<'\n';
	for(x=0; x < ctcSize; ++x)
	{
		for(it=CTC[x].begin(), iend=CTC[x].end(); it < iend; ++it)
			out<<*it<<' ';
		out<<'\n';
	}
	return EXIT_SUCCESS;
}