Cod sursa(job #547440)

Utilizator feelshiftFeelshift feelshift Data 6 martie 2011 12:46:03
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.11 kb
// http://infoarena.ro/problema/biconex
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

#define maxSize 100002
#define from first
#define to second

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

int nodes,edges,nrConnected;
int low[maxSize];
vector<int> depth(maxSize,-1);
vector<int> biConnectedComponents[maxSize];
vector<int> graph[maxSize];
stack< pair<int,int> > edgeStack;

void depthFirst(int currentNode,int father,int currentDepth);
void saveEdges(int from,int to);

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);
	}

	depthFirst(1,0,0);

	out << nrConnected << "\n";

	int previous;
	vector<int>::iterator it,end;
	for(int i=1;i<=nrConnected;i++) {
		sort(biConnectedComponents[i].begin(),biConnectedComponents[i].end());

		previous = 0;
		end = biConnectedComponents[i].end();
		for(it=biConnectedComponents[i].begin();it!=end;++it)
			if(*it != previous)
				out << (previous = *it) << " ";
		out << "\n";
	}

	in.close();
	out.close();

	return (0);
}

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

	depth[currentNode] = low[currentNode] = currentDepth;

	for(it=graph[currentNode].begin();it!=end;++it) {
		if(*it != father)
			if(depth[*it] == -1) {
				edgeStack.push(make_pair(currentNode,*it));

				depthFirst(*it,currentNode,currentDepth+1);

				low[currentNode] = min(low[currentNode],low[*it]);

				if(low[*it] >= depth[currentNode])
					saveEdges(currentNode,*it);
			}
			else
				low[currentNode] = min(low[currentNode],depth[*it]);
	}
}

void saveEdges(int from,int to) {
	int currentFrom,currentTo;
	nrConnected++;

	do {
		currentFrom = edgeStack.top().from;
		currentTo = edgeStack.top().to;
		edgeStack.pop();

		biConnectedComponents[nrConnected].push_back(currentFrom);
		biConnectedComponents[nrConnected].push_back(currentTo);
	} while(currentFrom != from || currentTo != to);
}