Cod sursa(job #1471288)

Utilizator Master011Dragos Martac Master011 Data 13 august 2015 16:13:44
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.13 kb
#include<cstdio>
using namespace std;

const int mMax = 200000, nMax = 100000;
int val[mMax * 2], urm[mMax * 2], lst[nMax], st[nMax], nivel[nMax], low[nMax], sol[nMax * 2];
bool viz[nMax];
int n, m, nrc, vf, u, nrs, cnt, solPoz;

inline void adauga(int x, int y){
    val[nrc] = y;
    urm[nrc] = lst[x];
    lst[x] = nrc;
    nrc++;
}

void init(){
    for(int i = 0 ; i < n ; i ++) lst[i] = -1;
}


void dfs(int nod, int par){
    st[vf++] = nod;
    viz[nod] = 1;
    low[nod] = nivel[nod];

    int vec = val[lst[nod]], poz = lst[nod];
    while(vec > -1){
        if(vec != par){
            if(!viz[vec]){
                nivel[vec] = nivel[nod] + 1;
                dfs(vec, nod);

                low[nod] = low[nod] < low[vec] ? low[nod] : low[vec];

                if(low[vec] >= nivel[nod]){
                    u = st[--vf];
                    cnt = 1; nrs ++;
                    sol[solPoz + cnt] = u;

                    while(u != vec){
                        u = st[--vf]; ++ cnt;
                        sol[solPoz + cnt] = u;
                    }
                    ++cnt;
                    sol[solPoz + cnt] = nod;
                    sol[solPoz] = cnt;
                    solPoz += cnt + 1;
                }
            }else if(nivel[vec] < nivel[nod]){
                low[nod] = low[nod] < low[vec] ? low[nod] : low[vec];
            }
        }

        poz = urm[poz];
        vec = poz >= 0 ? val[poz] : -1;
    }

}
int main (){

    FILE *in = fopen("biconex.in","r");
    fscanf(in,"%d%d", &n ,&m);

    init();
    int x, y;
    for(int i = 0 ; i < m ; i++){
        fscanf(in,"%d%d", &x, &y);
        x--, y--;
        adauga(x,y);
        adauga(y,x);
    }

    for(int i = 0 ; i < n ; i++){
        if(!viz[i])
            dfs(i, - 1);
    }

    FILE *out = fopen("biconex.out","w");
    fprintf(out,"%d\n", nrs);

    int i = 0, tg;
    while(i < solPoz){
        cnt = sol[i++];
        tg = i + cnt;
        while(i < tg){
            fprintf(out,"%d ", sol[i] + 1);
            i++;
        }
        fprintf(out,"\n");
    }

    return 0;
}