Cod sursa(job #930552)

Utilizator taigi100Cazacu Robert taigi100 Data 27 martie 2013 18:30:58
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include<stdio.h>
#include<vector>
#include<stack>
#include<algorithm>

using namespace std;
#define max 100005
#define Min(a,b) ((a)<(b) ? (a):(b))
vector<int> roads[max],dfn,low;
int n,m;
vector< vector<int> > final;
stack< pair<int,int> > stk;

void shit(int a,int b)
{
	vector<int> res; int x,y;

	do
	{
		x=stk.top().first;y=stk.top().second;
		stk.pop();
		res.push_back(x); res.push_back(y);
	}while(x!=a || b!=y);
	final.push_back(res);
}
void DFS(int n,int fn,int number)
{
	low[n]=number;
	dfn[n]=number;
	for(vector<int>::iterator it=roads[n].begin(); it!=roads[n].end();it++)
	{
	   if(*it==fn) continue;
	   if(dfn[*it]==-1)
	   {
		   stk.push( make_pair(n,*it) );
		   DFS(*it,n,number+1);
		   low[n]=Min(low[n],low[*it]);
		   if( low[*it] >= dfn[n] )
			   shit(n,*it);
	   }
	   else
		   low[n]=Min(low[n],low[*it]);
	}
}
int main()
{
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);

	scanf("%d%d",&n,&m);
	for(;m>0;m--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		roads[x].push_back(y);
		roads[y].push_back(x);
	}

	dfn.resize(n+1),
		dfn.assign(n+1,-1);
	low.resize(n+1);
	DFS(1,0,0);

	printf("%d\n",final.size());

	for(size_t i=0;i<final.size();i++)
	{
		sort(final[i].begin(),final[i].end());
		final[i].erase(unique(final[i].begin(),final[i].end()),final[i].end());
		for(size_t j=0;j<final[i].size();j++)
			printf("%d ",final[i][j]);
		printf("\n");
	}
}