Cod sursa(job #575805)

Utilizator andrei.sfrentSfrent Andrei andrei.sfrent Data 8 aprilie 2011 19:12:33
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
#include <set>

using namespace std;

#define N 100000
#define M 200000

vector<int> g[N];
stack<pair<int, int> > sm;
int n, m;
int desc[N], low[N];
int t = 0;
int ncbc = 0;
set<int> cbc[M];

ofstream fo("biconex.out");

void citeste()
{
	ifstream fi("biconex.in");
	fi >> n >> m;
	int x, y;
	for(int i = 0; i < m; ++i)
	{
		fi >> x >> y;
		x--; y--;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	fi.close();
}

void dfs(int v, int tata)
{
	desc[v] = t; // timp de descoperire
	low[v] = t; // lowest desc
	t++;
	for(vector<int> :: iterator it = g[v].begin(); it != g[v].end(); ++it)
	{
		int u = *it;
		if(tata == u) continue;
		sm.push(pair<int, int>(v, u));
		if(desc[u] < 0)
		{
			dfs(u, v);
			if(low[v] > low[u]) low[v] = low[u];
			if(low[u] >= desc[v])
			{
				while(1)
				{
					pair<int, int> arc = sm.top();
					sm.pop();
					cbc[ncbc].insert(arc.first);
					cbc[ncbc].insert(arc.second);
					if(arc == pair<int, int>(v, u)) 
					{
						ncbc++;
						break;
					}
				}
			}
		}
		else
		{
			if(low[v] > desc[u]) low[v] = desc[u];
		}
	}
}

int main()
{
	citeste();

	for(int i = 0; i < n; ++i) desc[i] = -1;
	dfs(0, -1);
	
	fo << ncbc << endl;
	
	for(int i = 0; i < ncbc; ++i)
	{
		for(set<int> :: iterator it = cbc[i].begin(); it != cbc[i].end(); ++it)
			fo << ((*it) + 1) << " ";
		fo << endl;
	}

	fo.close();
	return 0;
}