Cod sursa(job #1906775)

Utilizator horiainfoTurcuman Horia horiainfo Data 6 martie 2017 16:19:55
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

struct Graf { int index, lowLink; bool inStack; vector<int> v; };

int n, index, nrComp;

Graf node[100002];
vector<int> comp[100002];

stack<int> myStack;

void GoVisit(int nod)
{
	node[nod].index = ++index;
	node[nod].lowLink = index;
	myStack.push(nod);
	node[nod].inStack = true;

	for (int i = 0; i < node[nod].v.size(); i++)
	{
		if (!node[node[nod].v[i]].index)
		{
			GoVisit(node[nod].v[i]);
			node[nod].lowLink = min(node[nod].lowLink, node[node[nod].v[i]].lowLink);
		}
		else if(node[node[nod].v[i]].inStack)
			node[nod].lowLink = min(node[nod].lowLink, node[node[nod].v[i]].index);
	}

	if (node[nod].index == node[nod].lowLink)
	{
		nrComp++;
		while (myStack.top() != nod)
		{
			comp[nrComp].push_back(myStack.top());
			node[myStack.top()].inStack = false;
			myStack.pop();
		}

		comp[nrComp].push_back(myStack.top());
		myStack.pop();
	}
}

int main()
{
	int m, n1, n2;

	fin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		fin >> n1 >> n2;
		node[n1].v.push_back(n2);
	}

	for (int i = 1; i <= n; i++)
		if (!node[i].index)
			GoVisit(i);

	fout << nrComp << '\n';
	for (int i = 1; i <= nrComp; i++)
	{
		for (int j = 0; j < comp[i].size(); j++)
			fout << comp[i][j] << ' ';
		fout << '\n';
	}

	return 0;
}