Cod sursa(job #670874)

Utilizator feelshiftFeelshift feelshift Data 30 ianuarie 2012 12:31:55
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 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];
vector<int> graph[MAXSIZE];
vector< set<int> > biConnectedComponent;
stack< pair<int,int> > edgesStack;

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

int main()
{
	in >> nodes >> edges;

	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 << biConnectedComponent.size() << "\n";

	vector< set<int> >::iterator end = biConnectedComponent.end();
	for(vector< set<int> >::iterator it=biConnectedComponent.begin();it!=end;++it)
	{
		set<int>::iterator endC = it->end();
		for(set<int>::iterator node=it->begin();node!=endC;++node)
			out << *node << " ";
		out << "\n";
	}

	out.close();

	return (0);
}

void depthFirst(int currentNode,int father,int currentDepth)
{
	vector<int>::iterator end = graph[currentNode].end();

	depth[currentNode] = lowPoint[currentNode] = currentDepth;

	for(vector<int>::iterator 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,currentNode,currentDepth+1);
				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);
					biConnectedComponent.push_back(currentComponent);
				}
			}
}