Cod sursa(job #1447466)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 4 iunie 2015 15:31:07
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <vector>
#include <stack>

#define NMax 100010

using namespace std;

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

int nodes, edges, prenum[NMax], low[NMax], inc, k;
bool mark[NMax], inStack[NMax];
vector<int> G[NMax], Sol[NMax];
stack<int> S;

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

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

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

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

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

		if (!mark[*it]) {
			TARJANdfs(*it);
			low[node] = getmin(low[node], low[*it]);
		}
		else
			if (inStack[*it])
				low[node] = getmin(low[node], prenum[*it]);

	}

	if (low[node] == prenum[node]) {

		int u;
		k++;
		do {
			u = S.top();
			Sol[k].push_back(u);
			inStack[u] = false;
			S.pop();
		} while (u != node);

	}
}

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])
			TARJANdfs(i);

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

	return 0;
}