Cod sursa(job #954823)

Utilizator gabrieligabrieli gabrieli Data 30 mai 2013 08:57:09
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <algorithm>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

const int MAXN = 100010;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");

vector <int> G[MAXN];
vector <vector <int>> CTC;
int dfsIdx[MAXN], lowIdx[MAXN], N, idx;
bool inStack[MAXN];
stack <int> vStack;

void DFS (int v)
{
	vStack.push (v);
	inStack[v] = true;
	dfsIdx[v] = lowIdx[v] = ++idx;
	for (auto &n : G[v])
		if (!dfsIdx[n])
		{
			DFS (n);
			lowIdx[v] = min (lowIdx[v], lowIdx[n]);
		}
		else if (inStack[n])
			lowIdx[v] = min (lowIdx[v], lowIdx[n]);

	if (lowIdx[v] == dfsIdx[v])
	{
		int x;
		CTC.push_back (vector <int>());
		do {
			x = vStack.top();
			vStack.pop();
			inStack[x] = false;

			CTC.back().push_back (x);
		} while (x != v);
	}
}

int main()
{
    int m;
    for (fin >> N >> m; m; --m)
	{
		int x, y;
		fin >> x >> y;
		G[x].push_back (y);
	}

	for (int v = 1; v <= N; ++v)
		if (!dfsIdx[v])
			DFS (v);

	fout << CTC.size() << '\n';
	for (auto &ctc : CTC)
	{
		for (auto &v : ctc)
			fout << v << ' ';
		fout << '\n';
	}

	return EXIT_SUCCESS;
}