Cod sursa(job #724215)

Utilizator feelshiftFeelshift feelshift Data 26 martie 2012 12:33:38
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2 kb
// http://infoarena.ro/problema/biconex
#include <fstream>
#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");

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

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

int main() {
	in >> nodes >> edges;
	
	pair<int,int> currentEdge;
	for(int i=1;i<=edges;i++) {
		in >> currentEdge.from >> currentEdge.to;
		
		graph[currentEdge.from].push_back(currentEdge.to);
		graph[currentEdge.to].push_back(currentEdge.from);
	}
	in.close();
	
	depthFirst(1,1,-1);
	
	out << components.size() << "\n";
	
	for(unsigned int i=0;i<components.size();i++) {
		set<int>::iterator it,end = components[i].end();
		
		for(it=components[i].begin();it!=end;++it)
			out << *it << " ";
		out << "\n";
	}
	out.close();
	
	return (0);
}

void depthFirst(int currentNode,int currentDepth,int father) {
	depth[currentNode] = lowPoint[currentNode] = currentDepth;
	
	vector<int>::iterator it,end = graph[currentNode].end();
	
	for(it=graph[currentNode].begin();it!=end;++it)
		if(*it != father)
			if(depth[*it])
				lowPoint[currentNode] = min(lowPoint[currentNode],depth[*it]);
			else {
				edgesStack.push(make_pair(currentNode,*it));
				depthFirst(*it,currentDepth+1,currentNode);
				lowPoint[currentNode] = min(lowPoint[currentNode],lowPoint[*it]);
				
				if(lowPoint[*it] >= depth[currentNode]) {
					pair<int,int> currentEdge;
					set<int> currentComponent;
					
					do {
						currentEdge = edgesStack.top();
						edgesStack.pop();
						
						currentComponent.insert(currentEdge.from);
						currentComponent.insert(currentEdge.to);
					} while(currentEdge.from != currentNode && currentEdge.to != *it);
					
					components.push_back(currentComponent);
				}
			}
}