Pagini recente » Cod sursa (job #2876564) | Cod sursa (job #2136598) | Cod sursa (job #2279347) | Cod sursa (job #1663539) | Cod sursa (job #1140517)
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
#define Nmax 100001
vector< int > v[Nmax];
vector< set<int> > l;
bool viz[Nmax];
vector< pair<int,int> > c;
int n, m, zz[Nmax], minim[Nmax], p;
int x, y;
void cmp(int x,int y)
{
int a, b;
set<int> s;
vector< pair<int, int> >::iterator it;
do{
it=c.end();
a=it->first; b=it->second;
s.insert(a); s.insert(b);
c.pop_back();
} while(a!=x || b!=y);
l.push_back(s);
}
void dfs(int nod,int tata,int inal)
{
int aux;
zz[nod]=minim[nod]=inal;
viz[nod]=1;
for(unsigned int i=0;i<v[nod].size();i++)
{
aux=v[nod][i];
if(aux==tata) continue;
if(!viz[aux])
{
c.push_back( make_pair(nod,aux) );
dfs(aux, nod, inal+1);
minim[nod]=(minim[nod] < minim[aux]) ? minim[nod] : minim[aux];
if(minim[aux]>=zz[nod])
cmp(nod, aux);
} else
minim[nod]=(minim[nod] < zz[aux]) ? minim[nod] : zz[aux];
}
}
int main()
{
freopen("biconex.in","rt",stdin);
freopen("biconex.out","wt",stdout);
scanf("%d%d",&n,&m);
for(register int i=0;i<m;i++)
{
scanf("%d %d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0,0);
printf("%d\n",l.size());
for(unsigned int i=0;i<l.size();i++)
{
for(set<int>::iterator it=l[i].begin(); it!=l[i].end(); it++)
if(*it) printf("%d ",*it);
printf("\n");
}
return 0;
}