Pagini recente » Cod sursa (job #1554702) | Cod sursa (job #2194815) | Cod sursa (job #1863478) | Cod sursa (job #1605160) | Cod sursa (job #1089829)
/*
~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);
}
}