Cod sursa(job #1089829)

Utilizator roby2001Sirius roby2001 Data 21 ianuarie 2014 23:04:53
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
/*
          ~Keep It Simple!~
*/

#include<stdio.h>
#include<list>

#define NMax 100005

using namespace std;

int N,M;
list<int> G[NMax], aux;
list< pair<int,int> > S;
list< list<int> > Final;

int Level[NMax],LowPoint[NMax];

void EmptyStack(int a,int b)
{
	int x,y;
	aux.clear();
	do
	{
		x = S.begin()->first;
		y = S.begin()->second;
		S.pop_front();
		aux.push_back(x);
		aux.push_back(y);
	} while( a!=x || b!=y );
	Final.push_back(aux);
}

void ComputeBiConnectedComps(int node, int root, int level )
{
	Level[node] = LowPoint[node] = level;

	for(list<int>::iterator it = G[node].begin(); it!=G[node].end(); it++)
	{
		if(*it == root)
			continue;
		if( !Level[*it] )
		{
			S.push_front(make_pair(node,*it));
			ComputeBiConnectedComps(*it,node,level+1);

			LowPoint[node] = min(LowPoint[node],LowPoint[*it]);

			if(LowPoint[*it] >= Level[node])
			{
				EmptyStack(node,*it);
			}
		}
		else
			LowPoint[node] = min(LowPoint[node],LowPoint[*it]);
	}
}

int main()
{
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);

	scanf("%d%d",&N,&M);

	int x,y;

	for(int i=1; i<=M; i++)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}

	ComputeBiConnectedComps(1,0,1);

	printf("%d\n",Final.size());
	for(list< list<int> >::iterator it=Final.begin(); it!=Final.end(); it++)
	{
		it->sort();
		list<int>::iterator j,i;
		for( i = it->begin(),j = i++; i != it->end(); i++, j++)
		{
			if(*j != *i)
			 printf("%d ",*j);
		}
			printf("%d\n",*j);
	}
}