Cod sursa(job #1552655)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 18 decembrie 2015 13:50:55
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <vector>
#include <stack>

#define NMax 100010

using namespace std;

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

int nodes, edges, conCom, prenum[NMax], low[NMax], pren, ncomp;
bool mark[NMax], isInStack[NMax];
vector<int> G[NMax], comp[NMax];
stack<int> strong;

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

void DFS(int node)
{
	mark[node] = true;

	prenum[node] = ++pren;
	low[node] = pren;

	strong.push(node);
	isInStack[node] = true;

	for (vector<int>::iterator it = G[node].begin(); it != G[node].end(); it++) {
		if (!mark[*it]) {
			DFS(*it);

			low[node] = getMin(low[node], low[*it]);
		}
		else if (isInStack[*it])
			low[node] = getMin(low[node], low[*it]);
	}

	if (prenum[node] == low[node]) {
		ncomp++;

		while (strong.top() != node) {
			comp[ncomp].push_back(strong.top());
			isInStack[strong.top()] = false;
			strong.pop();
		}

		comp[ncomp].push_back(strong.top());
		isInStack[strong.top()] = false;
		strong.pop();
	}
}

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

	int n1, n2;

	for (int i = 1; i <= edges; i++) {
		f >> n1 >> n2;

		G[n1].push_back(n2);
	}

	DFS(1);

	g << ncomp << "\n";
	for (int i = 1; i <= ncomp; i++) {
		for (vector<int>::iterator it = comp[i].begin(); it != comp[i].end(); it++)
			g << *it << " ";
		g << "\n";
	}
	return 0;
}