Cod sursa(job #1915552)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 8 martie 2017 21:36:56
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <vector>
#include <stack>

#define NMax 100010

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

int nodes, edges, preord[NMax], low[NMax], scc;
bool mark[NMax], inStack[NMax];
vector<int> G[NMax], answ[NMax];
stack<int> crtNodes;

int get_min(int a, int b)
{
	if (a < b)
		return a;
	return b;
}

void Tarjan(int node)
{
	mark[node] = true;
	preord[node] = ++preord[0];
	low[node] = preord[node];

	crtNodes.push(node);
	inStack[node] = true;

	for (auto& crt : G[node]) {
		if (!mark[crt]) {
			Tarjan(crt);

			low[node] = get_min(low[node], get_min(preord[node], low[crt]));
		}
		else if (inStack[crt])
			low[node] = get_min(low[node], get_min(preord[node], low[crt]));
	}

	if (preord[node] == low[node]) {
		scc++;
		while (crtNodes.top() != node) {
			int crt = crtNodes.top();
			answ[scc].push_back(crt);

			crtNodes.pop();
			inStack[crt] = false;
		}
		answ[scc].push_back(node);

		crtNodes.pop();
		inStack[node] = false;
	}
}

int main()
{
	f >> nodes >> edges;

	int n1, n2;
	for (int i = 1; i <= edges; i++) {
		f >> n1 >> n2;
		G[n1].push_back(n2);
	}

	Tarjan(1);

	g << scc << '\n';
	for (int i = 1; i <= scc; i++) {
		for (auto& a : answ[i])
			g << a << ' ';
		g << '\n';
	}
}