Cod sursa(job #567170)

Utilizator BalcauIonutFMI-Balcau Ionut BalcauIonut Data 29 martie 2011 19:45:50
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<stack>
#include<set>
using namespace std;

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

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 buildSet(int nr,int x,int y){
        pair<int,int> p,t;
        set<int> cur;
        p=make_pair(x,y);
        do{
        t=s.top();
        s.pop();
        cur.insert(t.first);
        cur.insert(t.second);
        }while(t!=p);
        sol.push_back(cur);
}

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(make_pair(x,y));
        if(dfn[y]==-1){
            biconex(y,x);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x]){
            //    printf("%d %d,",x,y);
                buildSet(nrcomp,x,y);
                nrcomp++;
            }
        }
        else if(y!=tx)
            low[x]=min(low[x],dfn[y]);
    }
}


void writeComp(){
    set<int>::iterator it;
    int i;
    for(i=0;i<nrcomp;++i){
        for(it=sol[i].begin();it!=sol[i].end();++it)
        printf("%d ",*it);
    printf("\n");
    }
}

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