Cod sursa(job #1414297)

Utilizator darrenRares Buhai darren Data 2 aprilie 2015 15:06:28
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

int N, M;
vector<int> V[100002];
int D[100002], minD[100002];
int ST[100002];
bool inST[100002];
vector<vector<int> > comp;

void Tarjan(int x)
{
	D[x] = ++D[0];
	minD[x] = D[x];
	ST[++ST[0]] = x;
	inST[x] = true;
	
	for (auto nod : V[x])
		if (!D[nod])
		{
			Tarjan(nod);
			minD[x] = min(minD[x], minD[nod]);
		}
		else if (inST[nod])
			minD[x] = min(minD[x], minD[nod]);
	
	if (minD[x] == D[x])
	{
		comp.push_back(vector<int>());
		while (true)
		{
			comp.back().push_back(ST[ST[0]]);
			inST[ST[ST[0]]] = false;
			--ST[0];
			if (ST[ST[0] + 1] == x) break;
		}
	}
}

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 (!D[i])
			Tarjan(i);
	
	fout << comp.size() << '\n';
	for (auto v : comp)
	{
		for (auto nod : v)
			fout << nod << ' ';
		fout << '\n';
	}
	
	fin.close();
	fout.close();
}