Cod sursa(job #1607992)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 21 februarie 2016 19:15:15
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
#include <cstdio>
#include <vector>
#define MAXN 100000
#define MAXM 200000
using namespace std;
vector <int> v[MAXN];
int vf, t, k, val[2*MAXM+1], next[2*MAXM+1], lista[MAXN+1], viz[MAXN+1], h[MAXN+1], hmin[MAXN+1], st[MAXM+1];
inline void add(int x, int y){
    if(v[x].size()==0){
        v[x].push_back(val[2*y+1]);
        v[x].push_back(val[2*y+2]);
    }else{
        if(val[2*y+1]==v[x][v[x].size()-1]){
            v[x].push_back(val[2*y+2]);
        }else{
            v[x].push_back(val[2*y+1]);
        }
    }
}
inline void adauga(int x, int y){
    t++;
    val[t]=y;
    next[t]=lista[x];
    lista[x]=t;
}
void dfs(int x){
    int p=lista[x];
    viz[x]=1;
    hmin[x]=h[x];
    while(p){
        if(viz[val[p]]==0){
            h[val[p]]=h[x]+1;
            st[++vf]=(p-1)/2;
            dfs(val[p]);
            if(hmin[val[p]]<h[x]){
                if(hmin[x]>hmin[val[p]]){
                    hmin[x]=hmin[val[p]];
                }
            }else{
                while(st[vf]!=(p-1)/2){
                    add(k, st[vf]);
                    vf--;
                }
                add(k, st[vf]);
                vf--;
                k++;
            }
        }else{
            if(hmin[x]>h[val[p]]){
                hmin[x]=h[val[p]];
            }
        }
        p=next[p];
    }
}
int main(){
    int n, m, x, y, i, j;
    FILE *fin, *fout;
    fin=fopen("biconex.in", "r");
    fout=fopen("biconex.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    for(i=0; i<m; i++){
        fscanf(fin, "%d%d", &x, &y);
        adauga(x, y);
        adauga(y, x);
    }
    dfs(1);
    fprintf(fout, "%d\n", k);
    for(i=0; i<k; i++){
        for(j=0; j<(int)v[i].size(); j++){
            fprintf(fout, "%d ", v[i][j]);
        }
        fprintf(fout, "\n");
    }
    fclose(fin);
    fclose(fout);
    return 0;
}