Cod sursa(job #869344)

Utilizator fhandreiAndrei Hareza fhandrei Data 1 februarie 2013 14:37:45
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 kb
// Include
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
using namespace std;

// Definitii
#define pb push_back
#define mp make_pair

#define edge pair<int, int>
#define from first
#define to second

// Constante
const int sz = (int)1e5+1;

// Functii
void dfs(int node, int father, int level);
void biconex(int currentFrom, int currentTo);

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

int nodes, edges;
int depth[sz], lowLevel[sz];

vector<int> graph[sz];
stack<edge> edgesStack;
vector<set<int> > answer;

// Main
int main()
{
	in >> nodes >> edges;
	
	int rFrom, rTo;
	for(int i=1 ; i<=edges ; ++i)
	{
		in >> rFrom >> rTo;
		graph[rFrom].pb(rTo);
		graph[rTo].pb(rFrom);
	}
	dfs(1, -1, 1);
	
	out << answer.size() << '\n';
	vector<set<int> >::iterator it, end=answer.end();
	for(it=answer.begin() ; it!=end ; ++it)
	{
		set<int> current = *it;
		set<int>::iterator sit, send=current.end();
		for(sit=current.begin() ; sit!=send ; ++sit)
			out << *sit << ' ';
		out << '\n';
	}
	
	in.close();
	out.close();
	return 0;
}

void dfs(int node, int father, int level)
{
	depth[node] = level;
	lowLevel[node] = level;
	vector<int>::iterator it, end=graph[node].end();
	
	for(it=graph[node].begin(); it!=end ; ++it)
	{
		if(*it == father)
			continue;
		
		if(depth[*it])
		{
			lowLevel[node] = min(lowLevel[node], lowLevel[*it]);
			continue;
		}
		
		edgesStack.push(mp(node, *it));
		dfs(*it, node, level+1);
		lowLevel[node] = min(lowLevel[node], lowLevel[*it]);
		
		if(level <= lowLevel[*it])
			biconex(node, *it);
	}
}

void biconex(int currentFrom, int currentTo)
{
	set<int> elements;
	edge current;
	do
	{
		current = edgesStack.top();
		edgesStack.pop();
		
		elements.insert(current.from);
		elements.insert(current.to);
	} while(current.from != currentFrom && current.to != currentTo);
	answer.pb(elements);
	elements.clear();
}