Cod sursa(job #928729)

Utilizator FayedStratulat Alexandru Fayed Data 26 martie 2013 17:29:54
Problema Componente biconexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.13 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#include <utility>
#include <cstdlib>
#define NMAX 100100
using namespace std;

typedef pair <int,int> pereche;
int *Graf[NMAX];
stack < pereche > ST;
vector < vector < int > > Sol;
int dfn[NMAX],low[NMAX];
int n,m,nr;
int degree[NMAX];

inline void citesc(){

    int x,y;
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&n,&m);
    while(m){

        scanf("%d%d",&x,&y);
        degree[x]++;
        degree[y]++;
    --m;
    }
    for(register int i=1;i<=n;degree[i++]=0)
        Graf[i] = (int*)malloc(degree[i]*sizeof(int));
    fseek(stdin,0,SEEK_SET);
    scanf("%d%d",&n,&m);

    for(register int i=1;i<=m;++i){

        scanf("%d%d",&x,&y);
        Graf[x][++degree[x]] = y;
        Graf[y][++degree[y]] = x;
    }
}

void scot_muchii(int u,int v){ // scot toate muchiile din stiva pana intalnesc muchia din comp biconexa

    vector < int > Temp;
    int tu, tv;

    do{
        tu = ST.top().first;
        tv = ST.top().second;
        ST.pop();
        Temp.push_back(tu);
        Temp.push_back(tv);
    } while(tu!=u || tv!=v);
    Sol.push_back(Temp);
}

void Biconex(int n,int father,int num){

    int u;
    low[n] = dfn[n] = num;
    for(register int i=1;i<=degree[n];++i){
            u = Graf[n][i];
        if(u!=father)
            if(dfn[u] == -1){ // daca nu am vizitat inca nodul
            ST.push(pereche(n,u));
            Biconex(u,n,num+1);
            low[n] = min(low[n],low[u]);
            if(low[u] >= dfn[n])
                scot_muchii(n,u);
            }
        else low[n] = min(low[n],dfn[u]);
    }
}

int main(){

    citesc();
    for(register int i=1;i<=n;++i)
    dfn[i] = -1;
    Biconex(1,0,0);
    printf("%d\n",Sol.size());
    for(register int i=0;i<Sol.size();++i){
        sort(Sol[i].begin(),Sol[i].end());
        Sol[i].erase(unique(Sol[i].begin(),Sol[i].end()),Sol[i].end());

        for(register int j=0;j<Sol[i].size();++j)
            printf("%d ",Sol[i][j]);
            printf("\n");
    }

return 0;
}