Cod sursa(job #419503)

Utilizator laserbeamBalan Catalin laserbeam Data 17 martie 2010 17:02:27
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <bitset>
#include <algorithm>

using namespace std;
#define NMAX 100005
#define min(a,b) (a<b?a:b)

int depth[NMAX], low[NMAX];
vector <int> G[NMAX];
stack < pair <int, int> > S;
vector < vector <int> > rez;
int n, cate;

void makeComp(int x, int y)
{
	int ax, ay;
	vector <int> Aux;
	do
	{
		ax = S.top().first;
		ay = S.top().second;
		S.pop();
		Aux.push_back(ax);
		Aux.push_back(ay);
	} while (ax != x || ay != y);
	sort(Aux.begin(), Aux.end());
	vector<int>::iterator it = unique(Aux.begin(), Aux.end());
	Aux.resize( it - Aux.begin());
	rez.push_back(Aux);
}

void df(int nod, int parent, int adanc)
{
	depth[nod] = low[nod] = adanc;
	vector<int>::iterator it;
	
	for(it = G[nod].begin(); it != G[nod].end(); ++it)
	{
		if (*it == parent) continue;
		if (depth[*it] == -1)
		{
			S.push(make_pair(nod, *it));
			df(*it, nod, adanc+1);
			low[nod] = min(low[nod], low[*it]);
			if ( low[*it] >= depth[nod])
				makeComp(nod, *it);
		} else {
			low[nod] = min(low[nod], low[*it]);
		}
	}
}

int main()
{
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
	
	int mm;
	scanf("%d %d ", &n, &mm);
	for (;mm;--mm)
	{
		int x,y;
		scanf("%d %d ", &x, &y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	for (int i = 1; i <= n; ++i) depth[i] = -1;
	
	df(1,0,0);
	
	cate = rez.size();
	printf("%d\n", cate);
	for (int i = 0; i < cate; ++i)
	{
		for (vector<int>::iterator it = rez[i].begin(); it != rez[i].end(); ++it)
			printf("%d ", *it);
		printf("\n");
	}
}