Cod sursa(job #703758)

Utilizator darrenRares Buhai darren Data 2 martie 2012 14:15:12
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <vector>

using namespace std;

int N, M;
vector<int> V[100002];
int W[100002], Wnow[100002];
int ST[100002];
vector<vector<int> > R;
bool inQ[100002];

void Tarjan(int x)
{
	ST[++ST[0]] = x;
	inQ[x] = true;
	
	W[x] = ++W[0];
	Wnow[x] = W[0];
	
	for (vector<int>::iterator it = V[x].begin(); it != V[x].end(); ++it)
	{
		if (!W[*it])
			Tarjan(*it);
		if (inQ[*it])
			Wnow[x] = min(Wnow[x], Wnow[*it]);
	}
	
	if (W[x] == Wnow[x])
	{
		R.push_back(vector<int>());
		while (ST[ST[0]] != x)
		{
			R.back().push_back(ST[ST[0]]);
			inQ[ST[ST[0]]] = false;
			--ST[0];
		}
		R.back().push_back(x);
		inQ[x] = false;
		--ST[0];
	}
}

int main()
{
	ifstream fin("ctc.in");
	ofstream fout("ctc.out");
	
	fin >> N >> M;
	for (int i = 1, nod1, nod2; i <= M; ++i)
	{
		fin >> nod1 >> nod2;
		V[nod1].push_back(nod2);
	}
	
	for (int i = 1; i <= N; ++i)
		if (!W[i])
			Tarjan(i);
	
	fout << R.size() << '\n';
	for (int i = 0; i < R.size(); ++i)
	{
		for (vector<int>::iterator it = R[i].begin(); it != R[i].end(); ++it)
			fout << *it << ' ';
		fout << '\n';
	}
	
	fin.close();
	fout.close();
}