Cod sursa(job #383610)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 17 ianuarie 2010 12:00:08
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include<cstdio>
#include<vector>
using namespace std;
#define pb push_back
#include<algorithm>
#define N 100001
#define minn(a,b) ((a<b)? (a):(b))
vector <int> a[N];
vector <int> rez[N];
int n,m,dep[N],low[N],x,y,st[N][2],nr;
bool viz[N];
void citire()
{
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1; i<=m; ++i)
	{
		scanf("%d%d",&x,&y);
		a[x].pb(y);
		a[y].pb(x);
	}
}
void solutie(int x0,int y0)
{
	int x,y;
	do
	{
		x=st[st[0][0]][0];
		y=st[st[0][0]][1];
		rez[nr].pb(x);
		rez[nr].pb(y);
		--st[0][0];
	}
	while (x!=x0||y!=y0);
	++nr;
}
void dfs(int n)
{
	viz[n]=true;
	low[n]=dep[n];
	size_t g=a[n].size();
	for (size_t i=0; i<g; ++i)
	{
		if (!viz[a[n][i]])
		{
			dep[a[n][i]]=1+dep[n];
			st[++st[0][0]][0]=n;
			st[st[0][0]][1]=a[n][i];
			dfs(a[n][i]);
			low[n]=minn(low[a[n][i]],low[n]);
			if (low[a[n][i]]>=dep[n])
				solutie(n,a[n][i]);
		}
		else
			low[n]=minn(low[n],dep[a[n][i]]);
	}
}
void afis()
{
	printf("%d\n",nr);
	for (int i=0; i<nr; ++i)
	{
		sort(rez[i].begin(),rez[i].end());
		rez[i].erase(unique(rez[i].begin(),rez[i].end()),rez[i].end());
		size_t g=rez[i].size();
		for (size_t j=0; j<g; ++j)
			printf("%d ",rez[i][j]);
		printf("\n");
	}
}
int main()
{
	citire();
	dfs(1);
	afis();
	return 0;
}