Pagini recente » Cod sursa (job #2762924) | Cod sursa (job #2070473) | Cod sursa (job #2976260) | Cod sursa (job #1202475) | Cod sursa (job #1990878)
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
const int nmax=1e5+5;
typedef pair<int,int> ii;
vector<int> adj[nmax],dfn,low;
vector< vector<int> > c;
stack<ii> stk;
inline int min(int a,int b)
{
if(a>b)
return b;
return a;
}
inline void cache_bc(int x,int y)
{
vector<int> con;
int tx,ty;
do
{
tx=stk.top().first;
ty=stk.top().second;
stk.pop();
con.push_back(tx);
con.push_back(ty);
}while(tx!=x||ty!=y);
c.push_back(con);
}
inline void df(int node,int fn,int number)
{
vector<int>::iterator it;
dfn[node]=low[node]=number;
for(it=adj[node].begin();it!=adj[node].end();++it)
{
if(*it==fn)
continue;
if(dfn[*it]==-1)
{
stk.push(ii(node,*it));
df(*it,node,number+1);
low[node]=min(low[node],low[*it]);
if(low[*it]>=dfn[node])
cache_bc(node,*it);
}
else
low[node]=min(low[node],dfn[*it]);
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
int x,i,j,y,n,m;
scanf("%d%d",&n,&m);
dfn.resize(n+1);
low.resize(n+1);
dfn.assign(n+1,-1);
for(i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
adj[x].push_back(y);
adj[y].push_back(x);
}
df(1,0,0);
printf("%d\n",c.size());
for(i=0;i<c.size();++i)
{
sort(c[i].begin(),c[i].end());
c[i].erase(unique(c[i].begin(),c[i].end()),c[i].end());
for(j=0;j<c[i].size();++j)
printf("%d ",c[i][j]);
printf("\n");
}
}