Cod sursa(job #1257477)

Utilizator victor_crivatCrivat Victor victor_crivat Data 7 noiembrie 2014 20:02:34
Problema Componente biconexe Scor 12
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#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';
}

}