Cod sursa(job #669607)

Utilizator feelshiftFeelshift feelshift Data 27 ianuarie 2012 13:44:33
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
// http://infoarena.ro/problema/ctc
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

const int MAXSIZE = 100001;

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

int nodes,edges,nodeCount,answer;
int indexx[MAXSIZE];
int lowLink[MAXSIZE];
bool inStack[MAXSIZE];
vector<int> graph[MAXSIZE];
stack<int> nodesStack;
vector< vector<int> > components;

void tarjan(int node);

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

	int from,to;
	for(int i=1;i<=edges;i++)
	{
		in >> from >> to;
		graph[from].push_back(to);
	}

	for(int i=1;i<=nodes;i++)
		if(!indexx[i])
			tarjan(i);

	out << answer << "\n";

	vector< vector<int> >::iterator end = components.end();
	vector<int>::iterator endC;

	for(vector< vector<int> >::iterator it=components.begin();it!=end;++it)
	{
		endC = it->end();
		for(vector<int>::iterator node=it->begin();node!=endC;++node)
			out << *node << " ";
		out << "\n";
	}

	return (0);
}

void tarjan(int currentNode)
{
	indexx[currentNode] = lowLink[currentNode] = ++nodeCount;

	inStack[currentNode] = true;
	nodesStack.push(currentNode);

	vector<int>::iterator end = graph[currentNode].end();

	for(vector<int>::iterator it=graph[currentNode].begin();it!=end;++it)
		if(!indexx[*it])
			{
				tarjan(*it);
				lowLink[currentNode] = min(lowLink[currentNode],lowLink[*it]);
			}
			else
				if(inStack[*it])
					lowLink[currentNode] = min(lowLink[currentNode],indexx[*it]);

	if(indexx[currentNode] == lowLink[currentNode])
	{
		answer++;
		int node = 0;
		vector<int> currentComponent;

		while(node != currentNode)
		{
			node = nodesStack.top();
			currentComponent.push_back(node);
			inStack[node] = false;
			nodesStack.pop();
		}

		components.push_back(currentComponent);
	}
}