Cod sursa(job #1257441)

Utilizator victor_crivatCrivat Victor victor_crivat Data 7 noiembrie 2014 19:19:58
Problema Componente biconexe Scor 12
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 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[1000];
vector<pair<int,int> >q[mare];
bool used[mare],c[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 j,int i)
{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 (*it!=t[x]&&niv[x]>niv[*it]) push(*it,x);
if(used[*it]==false)
{niv[*it]=niv[x]+1;
t[*it]=x;
if (x==rad) nr++;
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));
        }while((a!=x||b!=*it)&&(a!=*it||b!=x)&&(a!=0||b!=0));
        }
}
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);
 if (nr > 1) c[rad] = true;
        else c[rad] = false;
}
g<<nrx;
}