Cod sursa(job #716742)

Utilizator feelshiftFeelshift feelshift Data 19 martie 2012 10:34:16
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 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");

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)
		if(*it != father)
			if(depth[*it])
				lowPoint[currentNode] = min(lowPoint[currentNode],depth[*it]);
			else {
				nodesStack.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 = nodesStack.top();
						nodesStack.pop();
						
						currentComponent.insert(currentEdge.from);
						currentComponent.insert(currentEdge.to);					
					} while(currentEdge.from != currentNode && currentEdge.to != *it);
					
					components.push_back(currentComponent);
				}
			}
}