Cod sursa(job #284339)

Utilizator cotofanaCotofana Cristian cotofana Data 21 martie 2009 17:26:44
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <cstdio>
#include <string>
#include <stack>
#include <list>
#include <algorithm>
#define dim 100100

using namespace std;

struct nod
{
	int nr;
	nod *urm;
};
int n, m, fol[dim], nivel[dim], ct=0;
nod *prim[dim];
stack< pair<int, int> > s;
list<int> l[dim];

void add(nod *&p, int nr)
{
	nod *n1=new nod;
	n1->nr=nr;
	n1->urm=p;
	p=n1;
}

void el_st(int x1, int x2)
{
	int nd1, nd2;
	do
	{
		nd1=s.top().first;
		nd2=s.top().second;
		s.pop();
		l[ct].push_back(nd1);
		l[ct].push_back(nd2);
	} while ((nd1!=x1 || nd2!=x2) && (nd1!=x2 || nd2!=x1));
	ct++;
}

void dfs(int x, int par, int niv, int &niv_min)
{
	if (fol[x]) niv_min=nivel[x];
	else
	{
		int aux;
		nod *cur;
		
		fol[x]=1;
		nivel[x]=niv;
		niv_min=niv;
		
		cur=prim[x];
		while (cur)
		{
			if (cur->nr!=par)
			{
				if (nivel[cur->nr]<nivel[x])
				{
					s.push(make_pair(x, cur->nr));
					dfs(cur->nr, x, niv+1, aux);
					if (aux<niv_min) niv_min=aux;
					if (aux>=niv) el_st(x, cur->nr);
				}
			}
			cur=cur->urm;
		}
	}
}

int main()
{
	int i, a, b;
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
	scanf("%d %d\n", &n, &m);
	for (i=1; i<=m; i++)
	{
		scanf("%d %d\n", &a, &b);
		add(prim[a], b);
		add(prim[b], a);
	}
	dfs(1, -1, 1, a);
	printf("%d\n", ct);
	for (i=0; i<ct; i++)
	{
		memset(fol, 0, (n+1)*sizeof(int));
		for (list<int>::iterator it=l[i].begin(); it!=l[i].end(); it++)
			if (!fol[*it])
				printf("%d ", *it), fol[*it]=1;
		printf("\n");
	}
	return 0;
}