Pagini recente » Cod sursa (job #1401728) | Cod sursa (job #2450855) | Cod sursa (job #2076775) | Cod sursa (job #253539) | Cod sursa (job #2261752)
#include <bits/stdc++.h>
#define Nmax 100001
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
list <int> G[Nmax];
int dfn[Nmax];
int low[Nmax];
int N,nr,n;
vector < vector<int> > ans;
stack < pair <int,int> > st;
vector <int> v;
void DFS(int x, int t)
{
list <int> :: iterator it;
dfn[x]=low[x]=++N;
for(it=G[x].begin();it!=G[x].end();it++)
{
if(*it!=t)
{
if(dfn[*it]==-1)
{
st.push({*it,x});
DFS(*it,x);
low[x]=min(low[x],low[*it]);
if(low[*it]>=dfn[x])
{
nr++;
v.clear();
int tx,ty;
do
{
tx=st.top().first;
ty=st.top().second;
st.pop();
v.push_back(tx);
v.push_back(ty);
}while(tx!=*it or ty!=x);
ans.push_back(v);
}
}
else if(*it!=t)
low[x]=min(low[x],dfn[*it]);
}
}
}
int main()
{
int m,i,j;
f>>n>>m;
for(int con=1;con<=m;con++)
{
f>>i>>j;
G[i].push_back(j);
G[j].push_back(i);
}
fill(dfn+1,dfn+n+1,-1);
fill(low+1,low+n+1,-1);
DFS(1,-1);
g<<nr<<'\n';
for(i=0;i<nr;i++)
{
sort(ans[i].begin(),ans[i].end());
ans[i].erase(unique(ans[i].begin(),ans[i].end()),ans[i].end());
for(j=0;j<ans[i].size();j++)
g<<ans[i][j]<<' ';
g<<'\n';
}
return 0;
}