Pagini recente » Cod sursa (job #1238263) | Cod sursa (job #1556246) | Cod sursa (job #2036189) | Cod sursa (job #1687318) | Cod sursa (job #669079)
Cod sursa(job #669079)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
int a,b;
int dpt[100001],lp[100001];
stack <pair <int,int> > s;
vector <int> g[100001];
vector <vector <int> > c;
void cache_bc(int x,int y)
{
vector <int> con;
int tx,ty;
do
{
tx=s.top().first;
ty=s.top().second;
s.pop();
con.push_back(tx);
con.push_back(ty);
}
while (tx!=x||ty!=y);
c.push_back(con);
}
void dfs(int x,int f,int d)
{
vector <int>::iterator it;
dpt[x]=lp[x]=d;
for (it=g[x].begin();it!=g[x].end();++it)
{
if (*it==f)
continue;
if (dpt[*it]==-1)
{
s.push(make_pair(x,*it));
dfs(*it,x,d+1);
lp[x]=min(lp[x],lp[*it]);
if (lp[*it]>=dpt[x])
{
a=x;
b=*it;
cache_bc(x,*it);
}
}
else
lp[x]=min(lp[x],dpt[*it]);
}
}
int main()
{
int i,j,n,m,x,y;
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
for (;m>0;--m)
{
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
memset(dpt,-1,sizeof(dpt));
dfs(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");
}
return 0;
}