Cod sursa(job #1915596)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 8 martie 2017 21:45:55
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 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, p;
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] = ++p;
	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);
	}

	for (int i = 1; i <= nodes; i++)
		if (!mark[i])
			Tarjan(i);

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