Pagini recente » Cod sursa (job #341372) | Cod sursa (job #941192) | Cod sursa (job #1120781) | Cod sursa (job #2890718) | Cod sursa (job #1257477)
#include <fstream>
#include <vector>
#define mp make_pair
#define pb push_back
#define mare 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int>v[mare];
vector<pair<int,int> >q[mare];
vector<pair<int,int> > ::iterator it;
bool used[mare];
int x,y,m,n,niv[mare],l[mare],t[mare],rad,nr,i,stiv[mare][2],a,b,lung,nrx=0;
void push(int i,int j)
{stiv[++lung][0]=i;
stiv[lung][1]=j;
}
void pop(int &a,int &b,int &lung)
{
a=stiv[lung][0];
b=stiv[lung][1];
}
void df(int x)
{vector <int>::iterator it;
used[x]=true;
l[x]=niv[x];
for (it=v[x].begin();it!=v[x].end();it++)
{
if(used[*it]==false)
{push(*it,x);
niv[*it]=niv[x]+1;
t[*it]=x;
df(*it);
if (l[x] > l[*it]) l[x] = l[*it];
if (l[*it] >= niv[x])
{nrx++;
do
{
pop(a,b,lung);
q[nrx].pb(mp(a,b));
lung--;
}while((a!=*it||b!=*it)&&(a!=x||b!=x)&&lung>1);
}
}
else if (*it!=t[x]&& l[x]> niv[*it]) l[x] = niv[*it];
}}
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 (!used[i])
{niv[i]=1;
rad=i;
nr=0;
df(i);
}
int j;
g<<nrx<<'\n';
for (i=1;i<=nrx;i++)
{for (it=q[i].begin();it!=q[i].end();it++)
g<<(*it).first<<" "<<(*it).second<<" ";
g<<'\n';
}
}