Cod sursa(job #678940)

Utilizator razvan2006razvan brezulianu razvan2006 Data 12 februarie 2012 16:15:49
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <vector>
using namespace std;
#define nmax 100010

vector <int> g[nmax], sol[nmax];
int n, m, cnt, u[nmax], lev[nmax], levacc[nmax], s1[nmax], s2[nmax], h, t[nmax], st[nmax];

void df(int nod)
{
	u[nod]=1;
	levacc[nod]=lev[nod];
	int i, v;
	for (i=0; i<g[nod].size(); i++)
	{
		v=g[nod][i];
		if (t[nod]!=v)
		{
			if (u[v])
			{
				if (lev[v]<lev[nod]) 
				{
					s1[++h]=nod;
					s2[h]=v;
				}
				levacc[nod]=min(levacc[nod], lev[v]);
			} else
			{
				t[v]=nod;
				lev[v]=lev[nod]+1;
				s1[++h]=nod;
				s2[h]=v;
				df(v);
				if (levacc[v]>=lev[nod])
				{
					cnt++;
					if (!(s1[h]==nod && s2[h]==v))
						while (!(s1[h]==nod && s2[h]==v))
						{
							if (st[s1[h]]!=cnt) sol[cnt].push_back(s1[h]);
							st[s1[h]]=cnt;
							h--;
						} else
						if (st[s2[h]]!=cnt)
						{
							sol[cnt].push_back(s2[h]);
							st[s2[h]]=cnt;
						}
					if (st[s1[h]]!=cnt)
					{
						sol[cnt].push_back(s1[h]);
						st[s1[h]]=cnt;
					}
					h--;
				}
				levacc[nod]=min(levacc[nod], levacc[v]);
			}
		}
	}
}

int main()
{
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	scanf("%d %d", &n, &m);
	int i, j, x, y;
	for (i=1; i<=m; i++)
	{
		scanf("%d %d", &x, &y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	lev[1]=1;
	df(1);
	printf("%d\n",cnt);
	for (i=1; i<=cnt; i++) 
	{
		for (j=0; j<sol[i].size(); j++) printf("%d ",sol[i][j]);
		printf("\n");
	}
}