Cod sursa(job #419494)

Utilizator laserbeamBalan Catalin laserbeam Data 17 martie 2010 16:46:07
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <bitset>

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;
bitset<NMAX> viz;
int n;

void makeComp(int x, int y)
{
	viz.reset();
	int ax, ay;
	do
	{
		ax = S.top().first;
		ay = S.top().second;
		S.pop();
		viz[ax] = 1;
		viz[ay] = 1;
	} while (ax != x || ay != y);
	for (int i = 1; i <= n; ++i)
		if (viz[i]) printf("%d ",i);
	printf("\n");
	
}

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], depth[*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);
	
	
}