Pagini recente » Clasamentul arhivei de probleme | Cod sursa (job #1095006) | Cod sursa (job #3194160) | Cod sursa (job #389270) | Cod sursa (job #2404622)
#include <fstream>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int> v[100005];
vector < pair<int,int> > st;
vector <int> ans[100001];
int q[100005],niv[100005],low[100005],sol[100005],t[100005],rad,nr,ans2,ans1,n,m,i,x,y,ansnr,j,nr2;
void df(int k) {
int i,x;
low[k]=niv[k];
for (i=0;i<v[k].size();i++) {
x=v[k][i];
if (!niv[x]) {
niv[x]=niv[k]+1;
t[x]=k;
df(x);
low[k]=min(low[k],low[x]);
if (low[x]>=niv[k]) nr++;
}
else if (x!=t[k]) low[k]=min(low[k],niv[x]);
}
}
void df2(int k) {
int i,x,a1,a2,j;
low[k]=niv[k];
for (i=0;i<v[k].size();i++) {
x=v[k][i];
if (x!=t[k] && niv[x]<niv[k]) st.push_back({x,k});
if (!niv[x]) {
niv[x]=niv[k]+1;
t[x]=k;
df2(x);
low[k]=min(low[k],low[x]);
if (low[x]>=niv[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]) g<<sol[j]<<" ";
g<<'\n';
}
}
else if (x!=t[k]) low[k]=min(low[k],niv[x]);
}
}
void init() {
int i;
for (i=1;i<=n;i++)
niv[i]=low[i]=t[i]=0;
}
int main()
{
f>>n>>m;
for(i=1; i<=m; i++)
{
f>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(i=1; i<=n; i++)
{
if(niv[i]==0)
{
niv[i]=1;
nr=0;
rad=i;
q[ans1]=i;
df(i);
if(nr>1){sol[i]=1;}
else sol[i]=0;
}
}
niv[1]=1;
df(1);
g<<nr<<'\n';
init();
niv[1]=1;
df2(1);
return 0;
}