Pagini recente » Cod sursa (job #3350745) | Cod sursa (job #1270896) | Cod sursa (job #3334011) | Cod sursa (job #1809111) | Cod sursa (job #3307637)
#include <bits/stdc++.h>
using namespace std;
vector <int> v[100555];
int d[100555];
int l[100555];
int p[100555];
vector <int> cbc[1000555];
vector <int> st;
int in;
void dfs(int u,int k)
{
d[u]=k;
l[u]=k;
for(auto a:v[u])
{
if(a!=p[u])
{
if(p[a]==0)
{
p[a]=u;
st.push_back(u);
st.push_back(a);
dfs(a,k+1);
l[u]=min(l[u],l[a]);
if(l[a]>=d[u])
{
++in;
bool ok=false;
while(ok==false && st.size()>0)
{
cbc[in].push_back(st[st.size()-1]);
cbc[in].push_back(st[st.size()-2]);
if(st[st.size()-1]==a && st[st.size()-2]==u)
{
ok=true;
}
st.pop_back();
st.pop_back();
}
}
}
else if(d[a]<d[u])
{
l[u]=min(l[u],d[a]);
st.push_back(u);
st.push_back(a);
}
}
}
}
int main()
{
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n,m,x,y;
cin>>n>>m;
for(int i=1;i<=m;++i)
{
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=1;i<=n;++i)
{
if(d[i]==0)
{
p[i]=-1;
dfs(i,1);
}
}
cout<<in<<"\n";
for(int i=1;i<=in;++i)
{
sort(cbc[i].begin(),cbc[i].end());
for(int h=0;h<cbc[i].size();++h)
{
if(h==0 || cbc[i][h]!=cbc[i][h-1])
{
cout<<cbc[i][h]<<" ";
}
}
cout<<"\n";
}
return 0;
}