Cod sursa(job #716751)

Utilizator feelshiftFeelshift feelshift Data 19 martie 2012 10:42:48
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.54 kb
// http://infoarena.ro/problema/biconex
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#include <set>
using namespace std;

#define from first
#define to second

const int MAXSIZE = 100001;

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

/*
	Folosim set pentru a evita inserarea
	si verificarea ulterioara a unui nod
	in lista nodurilor care formeaza
	componenta biconexa
*/

int currentNodes,edges;
int depth[MAXSIZE],lowPoint[MAXSIZE];
vector< vector<int> > graph;
vector< set<int> > components;
stack< pair<int,int> > nodesStack;

void depthFirst(int currentNode, int currentDepth,int father);

int main() {
	in >> currentNodes >> edges;
	
	graph.resize(currentNodes+1);
	
	int from,to;
	for(int i=1;i<=edges;i++) {
		in >> from >> to;
		
		graph[from].push_back(to);
		graph[to].push_back(from);
	}
	in.close();
	
	depthFirst(1,1,-1);
	
	out << components.size() << "\n";
	
	vector< set<int> >::iterator it,end = components.end();
	for(it=components.begin();it!=end;++it) {
		set<int>::iterator node,endC = it->end();
		
		for(node=it->begin();node!=endC;++node)
			out << *node << " ";
		out << "\n";
	}
	out.close();

	return (0);
}

void depthFirst(int currentNode, int currentDepth,int father) {
	vector<int>::iterator it,end = graph[currentNode].end();
	
	depth[currentNode] = lowPoint[currentNode] = currentDepth;
	
	for(it=graph[currentNode].begin();it!=end;++it)
		// verificam sa nu se intoarca de unde a plecat
		if(*it != father)
			if(depth[*it])	// daca a fost vizitat
				lowPoint[currentNode] = min(lowPoint[currentNode],depth[*it]);
			else {
				nodesStack.push(make_pair(currentNode,*it));	// punem muchia pe stiva				
				depthFirst(*it,currentDepth+1,currentNode);		// exploram nodul
				lowPoint[currentNode] = min(lowPoint[currentNode],lowPoint[*it]);	// retinem minimul
				
				// daca am identificat o componenta biconexa
				// (am gasit un drum de intoarcere de la
				// un urmas al nodului la acesta)
				if(lowPoint[*it] >= depth[currentNode]) {
					pair<int,int> currentEdge;
					set<int> currentComponent;
					
					// retinem si elimina din stiva toate muchiile
					// pana la muchia (currentNode,*it) inclusiv
					do {
						currentEdge = nodesStack.top();
						nodesStack.pop();
						
						currentComponent.insert(currentEdge.from);
						currentComponent.insert(currentEdge.to);					
					} while(currentEdge.from != currentNode && currentEdge.to != *it);
					
					components.push_back(currentComponent);
				}
			}
}