Pagini recente » Cod sursa (job #2613898) | Cod sursa (job #1652656) | Cod sursa (job #897124) | Cod sursa (job #2595842) | Cod sursa (job #374936)
Cod sursa(job #374936)
#include<stdio.h>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
#define pb push_back
#define fs first
#define sc second
#define mp make_pair
#define N 100010
int n;
vector<int> a[N],dfn,low;
vector< vector<int> > rez;
stack< pair<int,int> > st;
inline void citire()
{
int m,x,y;
scanf("%d%d",&n,&m);
for(int i=0; i<m; ++i)
{
scanf("%d%d",&x,&y);
a[x].pb(y);
a[y].pb(x);
}
dfn.assign(n+1,-1);
low.resize(n+1);
}
inline void extrag(int x,int y)
{
vector<int> con;
int tx,ty;
do
{
tx=st.top().fs;
ty=st.top().sc;
st.pop();
con.pb(tx);
con.pb(ty);
}while(tx!=x || ty!=y);
rez.pb(con);
}
void dfs(int nod,int fn,int num)
{
dfn[nod]=low[nod]=num;
for(size_t i=0,lim=a[nod].size(); i<lim; ++i)
{
if(a[nod][i]==fn)
continue;
if(dfn[a[nod][i]]==-1)
{
st.push(mp(nod,a[nod][i]));
dfs(a[nod][i],nod,num+1);
low[nod]=min(low[a[nod][i]],low[nod]);
if(low[a[nod][i]]==dfn[nod]+1 || low[a[nod][i]]==dfn[nod])
extrag(nod,a[nod][i]);
}
else
low[nod]=min(low[nod],low[a[nod][i]]);
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
citire();
dfs(1,0,0);
printf("%u\n",rez.size());
for(size_t i=0,lim=rez.size(); i<lim; ++i)
{
sort(rez[i].begin(),rez[i].end());
rez[i].erase(unique(rez[i].begin(),rez[i].end()),rez[i].end());
for(size_t j=0,lim1=rez[i].size(); j<lim1; ++j)
printf("%d ",rez[i][j]);
printf("\n");
}
return 0;
}