Cod sursa(job #567133)

Utilizator BalcauIonutFMI-Balcau Ionut BalcauIonut Data 29 martie 2011 19:18:28
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> a[100001];
vector< pair<int,int> > s;
vector< pair<int,int> > breakpoint;
int n,m,step=0,fii=0,nrcomp;
vector<int> dfn(100001,-1);
vector<int> low(100001,-1);

void readData(){
    int i,x,y;
    freopen("biconex.in","r",stdin);
    scanf("%d %d",&n,&m);
    for(i=0;i<m;++i){
    scanf("%d %d",&x,&y);
    a[x].push_back(y);
    a[y].push_back(x);
    }
}

void biconex(int x,int tx){
    int i,y;
    dfn[x]=low[x]=++step;
    for(i=0;i<a[x].size();++i){
        y=a[x][i];
        if(y!=tx && dfn[y]<dfn[x])
            s.push_back(make_pair(x,y));
        if(dfn[y]==-1){
            if(x==1)
                fii++;
            biconex(y,x);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x]){
            //    printf("%d %d,",x,y);
                breakpoint.push_back(make_pair(x,y));
                nrcomp++;
            }
        }
        else if(y!=tx)
            low[x]=min(low[x],dfn[y]);
    }
}


void afisare(int st, int fin){
    vector< pair<int,int> >::iterator it;
    sort(s.begin()+st,s.begin()+fin+1);
    for(it=s.begin()+st;it<=s.begin()+fin;++it)
    printf("(%d %d),",it->first,it->second);
}

int main(){
    readData();
    freopen("biconex.out","w",stdout);
    biconex(1,-1);
    printf("%d\n",nrcomp);
   return 0;
}