Pagini recente » Cod sursa (job #283096) | Cod sursa (job #1710430) | Cod sursa (job #2902224) | Cod sursa (job #741914) | Cod sursa (job #2002409)
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
struct Pair{
int a,b;
};
vector <int> G[N];
vector <Pair> Sol[N];
stack <Pair> st;
int Reach[N], check[N], h[N],cnt;
void dfs(int x, int t){
for(int i=0;i<G[x].size();i++){
int y=G[x][i];
if(Reach[y]==0){
h[y]=h[x]+1;
Reach[y]=h[y];
st.push({x,y});
dfs(y,x);
if(Reach[y]>Reach[x] or (Reach[x]==Reach[y] and h[x]==Reach[x])){
cnt++;
int f;
do{
f=st.top().a;
Sol[cnt].push_back(st.top());
st.pop();
} while(f!=x);
}
Reach[x]=min(Reach[x],Reach[y]);
}
else{
if(y!=t and h[y]<Reach[x]) Reach[x]=h[y];
}
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
int n,m,i,j,x,y;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
Reach[1]=h[1]=1;
dfs(1,1);
printf("%d\n",cnt);
for(i=1;i<=cnt;i++){
for(j=0;j<Sol[i].size();j++){
x=Sol[i][j].a;
y=Sol[i][j].b;
if(check[x]==0) printf("%d ",x);
if(check[y]==0) printf("%d ",y);
check[x]=check[y]=1;
}
for(j=0;j<Sol[i].size();j++){
x=Sol[i][j].a;
y=Sol[i][j].b;
check[x]=check[y]=0;
}
printf("\n");
}
/*printf("\n\n");
for(i=1;i<=n;i++) printf("%d ",Reach[i]);*/
return 0;
}