Cod sursa(job #716786)

Utilizator feelshiftFeelshift feelshift Data 19 martie 2012 11:43:53
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
// http://infoarena.ro/problema/ctc
#include <fstream>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;

const int MAXSIZE = 100001;

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

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

void tarjan(int currentNode);

int main() {
	freopen("ctc.in","rt",stdin);
//	freopen("ctc.out","wt",stdout);
	
	//in >> nodes >> edges;
	scanf("%d%d",&nodes,&edges);
	
	int from,to;
	for(int i=1;i<=edges;i++) {
		//in >> from >> to;
		scanf("%d%d",&from,&to);
		
		graph[from].push_back(to);
	}
	//in.close();
	
	for(int i=1;i<=nodes;i++)
		if(!indexx[i])
			tarjan(i);
	
	out << components.size() << "\n";
	
	vector< vector<int> >::iterator it,end = components.end();
	
	for(int i=0;i<components.size();i++) {
		for(int k=0;k<components[i].size();k++)
			out << components[i][k] << " ";
		out << "\n";
	}
	
	out.close();
	
	return (0);
}

void tarjan(int currentNode) {
	indexx[currentNode] = lowLink[currentNode] = ++nodeCount;
	
	inStack[currentNode] = true;
	nodesStack.push(currentNode);
	
	vector<int>::iterator it,end = graph[currentNode].end();
	
	for(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]) {
		int node = 0;
		vector<int> currentComponent;
		
		while(node != currentNode) {
			node = nodesStack.top();
			inStack[node] = false;
			nodesStack.pop();
			currentComponent.push_back(node);
		}
		
		components.push_back(currentComponent);
	}
}