Pagini recente » Cod sursa (job #3198482) | Cod sursa (job #3201189) | Cod sursa (job #491033) | Cod sursa (job #1789998) | Cod sursa (job #2401636)
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;
FILE*f=fopen("biconex.in","r");
FILE*g=fopen("biconex.out","w");
vector<int> a[NMAX];
vector<pair<int,int> > st;
int n,m,d[NMAX],low[NMAX],t[NMAX],nr,nr2,sol[NMAX];
void df(int k) {
int i,x;
low[k]=d[k];
for (i=0;i<a[k].size();i++) {
x=a[k][i];
if (!d[x]) { ///daca nodul x nu e vizitat
d[x]=d[k]+1;
t[x]=k; ///k e tatal lui x
df(x);
low[k]=min(low[k],low[x]);
if (low[x]>=d[k]) nr++; ///k - punct de articulatoe (nu pot sa ajung din x mai sus de k)
}
else if (x!=t[k]) low[k]=min(low[k],d[x]);
}
}
void df2(int k) {
int i,x,a1,a2,j;
low[k]=d[k];
for (i=0;i<a[k].size();i++) {
x=a[k][i];
if (x!=t[k] && d[x]<d[k]) st.push_back({x,k});
if (!d[x]) { ///daca nodul x nu e vizitat
d[x]=d[k]+1;
t[x]=k; ///k e tatal lui x
df2(x);
low[k]=min(low[k],low[x]);
if (low[x]>=d[k]) { ///k - punct de articulatie (nu pot sa ajung din x mai sus de k)
nr2=0;
do {
a1=st[st.size()-1].first;
a2=st[st.size()-1].second;
sol[++nr2]=a1;
sol[++nr2]=a2;
st.pop_back();
} while (!st.empty() && !(a1==x && a2==k || a1==k && a2==x));
sort(sol+1,sol+nr2+1);
for (j=1;j<=nr2;j++)
if (sol[j]!=sol[j-1]) fprintf(g,"%d ",sol[j]);
fprintf(g,"\n");
}
}
else if (x!=t[k]) low[k]=min(low[k],d[x]);
}
}
void init() {
int i;
for (i=1;i<=n;i++)
d[i]=low[i]=t[i]=0;
}
int main() {
int i,j,x,y;
fscanf(f,"%d%d",&n,&m);
for (i=1;i<=m;i++) {
fscanf(f,"%d%d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
d[1]=1;
df(1);
fprintf(g,"%d\n",nr);
init();
d[1]=1;
df2(1);
return 0;
}