Cod sursa(job #507743)

Utilizator feelshiftFeelshift feelshift Data 6 decembrie 2010 18:03:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.11 kb
// http://infoarena.ro/problema/ctc
#include <fstream>
#include <algorithm>
#include <vector>
#include <list>
#include <stack>
using namespace std;

int nodes,edges,counter,stronglyConnectedComponents;
vector< list<int> > graph;
stack<int> nodeStack;
vector<bool> inStack;
vector<int> indexx,lowlink,oneSolution;

vector< vector<int> > solution;

void read();
void tarjan(int toVisit);
void write();

int main() {
	read();
	
	for(int i=1;i<=nodes;i++)
		if(!indexx.at(i))	// daca nu a fost vizitat
			tarjan(i);
	
	write();	
	
	return (0);
}

void read() {
	ifstream in("ctc.in");
	int from,to;
	
	in >> nodes >> edges;
	graph.resize(nodes+1);
	inStack.resize(nodes+1);
	indexx.resize(nodes+1);
	lowlink.resize(nodes+1);
	
	for(int i=1;i<=edges;i++) {
		in >> from >> to;
		
		graph.at(from).push_back(to);
	}
	
	in.close();
}

void tarjan(int toVisit) {
	indexx.at(toVisit) = ++counter;
	lowlink.at(toVisit) = counter;
	
	nodeStack.push(toVisit);	// adaug in stiva nodul curent
	inStack.at(toVisit) = true;	// il marchez ca fiind in stiva
	
	for(list<int>::iterator it=graph.at(toVisit).begin();it!=graph.at(toVisit).end();it++)
		if(!indexx.at(*it)) {	// daca nu a fost vizitat
			tarjan(*it);
			lowlink.at(toVisit) = min(lowlink.at(toVisit),lowlink.at(*it));
		}
		else
			if(inStack.at(*it))
				lowlink.at(toVisit) = min(lowlink.at(toVisit),lowlink.at(*it));
	
	// daca s-a identificat o componenta tare conexa
	if(lowlink.at(toVisit) == indexx.at(toVisit)) {
		int node = NULL;
		oneSolution.clear();	// se goleste vectorul
		
		while(node != toVisit) {
			node = nodeStack.top();
			nodeStack.pop();	// se scoate nodul din stiva
			inStack.at(node) = false;
			
			oneSolution.push_back(node);
		}

		solution.push_back(oneSolution);	// se adauga solutia
		stronglyConnectedComponents++;	// creste numarul componentelor tare conexe
	}
	
}

void write() {
	ofstream out("ctc.out");
	int end;
	
	out << stronglyConnectedComponents << "\n";
	
	for(int i=0;i<stronglyConnectedComponents;i++) {
		end = solution.at(i).size();
		
		for(int k=0;k<end;k++)
			out << solution.at(i).at(k) << " ";
		out << "\n";	// cu endl nu intra in timp :)
	}
	
	out.close();
}