Pagini recente » Cod sursa (job #18785) | Cod sursa (job #1931757) | Cod sursa (job #2499378) | Cod sursa (job #984082) | Cod sursa (job #1980628)
#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;
bool viz[Nmax];
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();
fill(viz+1,viz+n+1,false);
int tx,ty;
do
{
tx=st.top().first;
ty=st.top().second;
st.pop();
if(!viz[tx]) {v.push_back(tx); viz[tx]=true;}
if(!viz[ty]) {v.push_back(ty); viz[ty]=true;}
}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++)
{
m=ans[i].size();
for(j=0;j<m;j++)
g<<ans[i][j]<<' ';
g<<'\n';
}
return 0;
}