Pagini recente » Cod sursa (job #348031) | Cod sursa (job #184029) | Cod sursa (job #706821) | Cod sursa (job #2112686) | Cod sursa (job #2285294)
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
vector <int> c[100004],v[100004];
vector < pair<int,int> > s;
int n,m,i,j,k,x,y,nr,poz,d[100004],l[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;
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, int y)
{
nr++;
poz=s.size()-1;
while ((s[poz].first!=x) || (s[poz].second!=y))
{
c[nr].push_back(s[poz].first);
c[nr].push_back(s[poz].second);
s.pop_back();
poz--;
}
c[nr].push_back(s[poz].first);
c[nr].push_back(s[poz].second);
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({x,v[x][i]});
p(v[x][i]);
if (l[x]<=d[v[x][i]])
r(x,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++)
{
sort (c[i].begin(),c[i].end());
printf ("%d ", c[i][0]);
k=c[i].size()-1;
for (j=1;j<=k;j++)
{
if (c[i][j]!=c[i][j-1])
printf ("%d ", c[i][j]);
}
printf ("\n");
}
return 0;
}