Pagini recente » Cod sursa (job #2086967) | Cod sursa (job #131699) | Cod sursa (job #963125) | Cod sursa (job #2409447) | Cod sursa (job #3193628)
#include <bits/stdc++.h>
std::ifstream cin("biconex.in");
std::ofstream cout("biconex.out");
int n,m,x,y,low[100010],v[100010],val,vmax;
std::vector<std::vector<int>>a;
std::vector<std::vector<int>>f;
std::vector<int>ans[100010];
void pleaca(int nod,int t)
{
v[nod]=low[nod]=++val;
for(auto x:a[nod])
{
if(x==t)
continue;
if(v[x])
low[nod]=std::min(low[nod],v[x]);
else
{
pleaca(x,nod);
f[nod].push_back(x);
low[nod]=std::min(low[nod],low[x]);
}
}
}
void creaza(int nod,int comp)
{
if(comp>vmax)
vmax=comp;
if(nod==1)
{
for(auto x:f[nod])
{
ans[vmax+1].push_back(nod);
if(low[x]!=v[nod])
{
ans[vmax+1].push_back(x);
creaza(x,vmax+2);
}
else
creaza(x,vmax+1);
}
return;
}
ans[comp].push_back(nod);
for(auto x:f[nod])
{
if(low[x]<v[nod])
creaza(x,comp);
else if(low[x]==v[nod])
{
ans[vmax+1].push_back(nod);
creaza(x,vmax+1);
}
else
{
ans[vmax+1].push_back(nod);
ans[vmax+1].push_back(x);
creaza(x,vmax+2);
}
}
}
int main()
{
cin>>n>>m;
a.resize(n+5);
f.resize(n+5);
for(int i=1;i<=m;++i)
{
cin>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
pleaca(1,-1);
creaza(1,0);
int vad=vmax;
for(int i=1;i<=vmax;++i)
if(ans[i].size()==1)
--vad;
cout<<vad<<'\n';
for(int i=1;i<=vmax;++i)
if(ans[i].size()!=1)
{
for(auto x:ans[i])
cout<<x<<' ';
cout<<'\n';
}
return 0;
}