Cod sursa(job #629792)

Utilizator ELHoriaHoria Cretescu ELHoria Data 3 noiembrie 2011 23:25:39
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int MAXN = 100002;
int  N , M , x , y , indecs;
vector< vector<int> > C; 
vector<int> G[MAXN] , lowlink , idx , con , in_stack;
stack<int> S;

void read_data()
{	fin>>N>>M;
	for(;M;M--)
		fin>>x>>y , G[x].push_back(y);
	idx.resize(N+1), lowlink.resize(N+1), in_stack.resize(N+1);
	idx.assign(N+1, -1), in_stack.assign(N+1, 0);
}

void tarjan(const int node)
{
	lowlink[node] = idx[node] = indecs;
	indecs++;
	S.push(node) , in_stack[node] = 1;
	for(vector<int>::const_iterator it=G[node].begin();it!=G[node].end();++it)
		if(idx[*it]==-1) tarjan(*it) , lowlink[node] = min(lowlink[node],lowlink[*it]);
		else
		if (in_stack[*it])
			lowlink[node] = min(lowlink[node],lowlink[*it]);

		if(idx[node]==lowlink[node])
		{
			int n;
			con.clear();
			do
			{	con.push_back( n = S.top());
				S.pop() , in_stack[node] = 0;
			} while(n!=node);
			C.push_back(con);
		}
}

void write_data()
{
	fout<<C.size()<<"\n";
	for(int i=0;i<(int)C.size();++i)
	{
		for(int j=0;j<(int)C[i].size();++j)
			fout<<C[i][j]<<' ';
		fout<<"\n";
	}
}

int main()
{
	read_data();
	for(int i=1;i<=N;++i)
		if(idx[i]==-1) 	tarjan(i);

	write_data();
	return 0;
}