Cod sursa(job #590583)

Utilizator theodora_maneaManea Theodora Maria theodora_manea Data 18 mai 2011 16:42:38
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <fstream>

#define max_n 100001
#define max_m 200001

using namespace std;

typedef struct point {
    int inf;
    point *leg;
};
point *g[max_n];
int u[max_n],t[max_n],l[max_n],st[max_m][2],nv[max_n];
int i,j,n,m,nr,x,y,nrc;


 ifstream f ("biconex.in");
 ofstream f2 ("biconex.out");


void adauga(int i,int j){
    point *p;
    p=new point;
    p->inf=i;
    p->leg=g[j];
    g[j]=p;
}

void push(int i,int j) {
     st[nr][0]=i;
     st[nr++][1]=j;
}

void pop (int &i,int &j) {
     i=st[--nr][0];
     j=st[nr][1];
}

void Df(int nod) {
    point *p;
    int x,y;
    u[nod]=1;
    l[nod]=nv[nod];
    for (p=g[nod]; p!=NULL; p=p->leg) {
        if (p->inf!=t[nod] && nv[nod]>nv[p->inf])
           push(p->inf,nod);
        if (!u[p->inf]) {
           nv[p->inf]=nv[nod]+1;
           t[p->inf]=nod;
           Df(p->inf);
        if (l[nod]>l[p->inf])
           l[nod]=l[p->inf];
        if (l[p->inf]>=nv[nod]) {
			nrc++;
           do {
                pop(x,y);
                //f2 << x <<' ' << y << ' ';
            }
            while (!(x==nod &&  y==p->inf) && !(x==p->inf && y==nod));
            //f2 << '\n';
        }
        }
        else
        if (p->inf!=t[nod] && l[nod]>nv[p->inf])
           l[nod]=nv[p->inf];
}
}



int main () {

    f >> n >> m;
    nr=0;
	nrc=0;
    for (i=1; i<=m; i++) {
        f >> x >> y;
        adauga(x,y);
        adauga(y,x);
    }

    for (i=1; i<=n; i++) {
        if (!u[i]) {
            nv[i]=1;
            Df(i);
        }
    }
	f2 << nrc << '\n';
	f.close();
	f2.close();
    return 0;
}