Cod sursa(job #703735)

Utilizator darrenRares Buhai darren Data 2 martie 2012 14:06:20
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 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;

void Tarjan(int x)
{
	ST[++ST[0]] = x;
	
	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);
		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]]);
			--ST[0];
		}
		R.back().push_back(x);
		--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);
	}
	
	Tarjan(1);
	
	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();
}