Cod sursa(job #927323)

Utilizator dragangabrielDragan Andrei Gabriel dragangabriel Data 25 martie 2013 18:54:37
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
#include<algorithm>
#define nmax 100005
using namespace std;
int m,rez,n,i,j,k,dfn[nmax],low[nmax],x,y,tata,nod,fiu;
vector<int>v[nmax],A[nmax];
stack<pair<int,int> >s;

void add(int nod,int tata)
{
	rez++;
	while (s.top().first!=nod && s.top().second!=tata)
	{
		A[rez].push_back(s.top().second);
		s.pop();
	}		
	A[rez].push_back(nod);
	A[rez].push_back(tata);
	s.pop();
}

void df(int nod,int tata)
{
	int fiu;
	dfn[nod]=low[nod]=dfn[tata]+1;
	for (int j=0;j<v[nod].size();j++)
	{
		fiu=v[nod][j];
		if (fiu!=tata)
		{
			if (!dfn[fiu])
			{
				s.push(make_pair(nod,fiu));
				df(fiu,nod);
				if (low[fiu]>=dfn[nod]) add(nod,fiu);
			}
			low[nod]=min(low[nod],low[fiu]);
		}
	}
}

int main()
{
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (i=1;i<=m;i++) scanf("%d %d",&x,&y),v[x].push_back(y),v[y].push_back(x);
	s.push(make_pair(1,0));
	df(1,0);
	printf("%d\n",rez);
	for (i=1;i<=rez;i++)
	{
		for (j=0;j<A[i].size();j++)
			printf("%d ",A[i][j]);
		printf("\n");
	}
	return 0;
}