Pagini recente » Cod sursa (job #245771) | Cod sursa (job #3177955) | Cod sursa (job #1343171) | Cod sursa (job #1446841) | Cod sursa (job #2722682)
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
stack < pair < int , int > > st;
vector <int> v[100100],sol[100100];
int ans,sl[200100],viz[100100],ant[100100],nivel[100100],tata[100100];
void solve(int nod)
{
ant[nod]=nivel[nod];
viz[nod]=1;
for(int i=0; i<v[nod].size(); i++)
{
int vecin=v[nod][i];
if(viz[vecin]==0)
{
viz[vecin]=1;
nivel[vecin]=nivel[nod]+1;
tata[vecin]=nod;
st.push({nod,vecin});
solve(vecin);
if(ant[vecin]<ant[nod])ant[nod]=ant[vecin];
if(ant[vecin]>=nivel[nod])
{
int T=0,st_nod,st_vecin;
ans++;
do
{
st_nod=st.top().first;
st_vecin=st.top().second;
st.pop();
T++;
sl[T]=st_nod;
T++;
sl[T]=st_vecin;
}
while(!st.empty() && !(st_nod==nod && st_vecin==vecin));
sort(sl+1,sl+T+1);
for(int j=1; j<=T; j++)
if(sl[j]!=sl[j-1])
sol[ans].push_back(sl[j]);
}
}
else
{
if(tata[nod]!=vecin && nivel[vecin]<ant[nod])ant[nod]=nivel[vecin];
}
}
}
int n,m,i,j,x,y;
int main()
{
f>>n>>m;
for(i=1; i<=m; i++)
{
f>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
nivel[1]=1;
solve(1);
g<<ans<<'\n';
for(i=1;i<=ans;i++)
{
for(j=0;j<sol[i].size();j++)
g<<sol[i][j]<<" ";
g<<'\n';
}
return 0;
}