Pagini recente » Cod sursa (job #2824982) | Cod sursa (job #2709517) | Cod sursa (job #1492818) | Cod sursa (job #377720) | Cod sursa (job #2285301)
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
vector <int> s,c[100004],v[100004];
int n,m,i,j,k,x,y,nr,poz,d[100004],l[100004],t[100004];
bool sel[100004];
void g (int x)
{
int i,k;
sel[x]=true;
k=v[x].size()-1;
d[x]=l[x];
for (i=0;i<=k;i++)
{
if (sel[v[x][i]]==false)
{
l[v[x][i]]=l[x]+1;
t[v[x][i]]=x;
g(v[x][i]);
}
else
{
if (l[v[x][i]]<d[x])
d[x]=l[v[x][i]];
}
}
for (i=0;i<=k;i++)
{
if (l[x]<l[v[x][i]])
{
if (d[x]>d[v[x][i]])
d[x]=d[v[x][i]];
}
}
return;
}
void r (int x)
{
nr++;
poz=s.size()-1;
while (s[poz]!=x)
{
c[nr].push_back(s[poz]);
s.pop_back();
poz--;
}
c[nr].push_back(s[poz]);
c[nr].push_back(t[s[poz]]);
s.pop_back();
return;
}
void p (int x)
{
int i,k,Max;
k=v[x].size()-1;
sel[x]=true;
Max=0;
for (i=0;i<=k;i++)
{
if (sel[v[x][i]]==false)
{
s.push_back(v[x][i]);
p(v[x][i]);
if (l[x]<=d[v[x][i]])
r(v[x][i]);
}
}
}
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);
}
l[1]=1;
g(1);
for (i=1;i<=n;i++)
sel[i]=false;
nr=0;
p(1);
printf ("%d\n", nr);
for (i=1;i<=nr;i++)
{
k=c[i].size()-1;
for (j=0;j<=k;j++)
printf ("%d ", c[i][j]);
printf ("\n");
}
return 0;
}