Cod sursa(job #530303)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 7 februarie 2011 14:43:11
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#define NMAX 100005
#define LMAX 200005
#define pb push_back
using namespace std;
int n,m,r,dad[NMAX],up[NMAX],lvl[NMAX],rez;
vector <int> A[NMAX],S[NMAX];
struct muchie{int a,b;};
muchie B[LMAX];
char viz[NMAX];
void read()
{
	scanf("%d%d",&n,&m);
	int i,x,y;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d",&x,&y);
		A[x].pb(y);
		A[y].pb(x);
	}
}
void dfs(int nod)
{
	viz[nod]=1;
	int i,fiu;
	up[nod]=lvl[nod];
	for (i=0; i<A[nod].size(); i++)
	{
		fiu=A[nod][i];
		if (!viz[fiu])
		{
			lvl[fiu]=lvl[nod]+1;
			dad[fiu]=nod;
			B[++r].a=nod; B[r].b=fiu;
			dfs(fiu);
			if (up[nod]>up[fiu]) up[nod]=up[fiu];
			if (up[fiu]>=lvl[nod])
			{
				rez++;
				while (B[r].a!=nod || B[r].b!=fiu)
				{
					S[rez].pb(B[r].a);
					S[rez].pb(B[r].b);
					r--;
				}
				S[rez].pb(B[r].a);
				S[rez].pb(B[r].b);
				r--;
			}
		}
		else
			if (dad[nod]!=fiu && lvl[fiu]<lvl[nod])
			{
				if (up[nod]>lvl[fiu]) up[nod]=lvl[fiu];
				B[++r].a=nod; B[r].b=fiu;
			}
	}
}
void show()
{
	printf("%d\n",rez);
	int i,j,val;
	for (i=1; i<=rez; i++)
	{
		sort(S[i].begin(),S[i].end());
		val=0;
		for (j=0; j<S[i].size(); j++)
			if (S[i][j]!=val)
			{
				printf("%d ",S[i][j]);
				val=S[i][j];
			}
		printf("\n");
	}
}
int main()
{
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	read();
	dfs(1);
	show();
	return 0;
}