Cod sursa(job #2174007)

Utilizator andrei.gramescuAndrei Gramescu andrei.gramescu Data 16 martie 2018 10:20:29
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
#define NMAX 100005
#define INF 2000000005
typedef pair<int, int> ii;

int n, m, solsz, time, d[NMAX], t[NMAX], low[NMAX];
vector<int> a[NMAX], sol[NMAX];
stack<ii> st;

void biconex(int source, int child) {
    solsz++;
    ii aux;
    aux.first = st.top().first;
    aux.second = st.top().second;

    while(aux.first != source && aux.second != child) {
        sol[solsz].push_back(aux.second);
        st.pop();
        aux.first = st.top().first;
        aux.second = st.top().second;
    }

    st.pop();
    sol[solsz].push_back(aux.second);
    sol[solsz].push_back(aux.first);
}

void DFS(int nod) {

    int i, child;

    time++;
    d[nod] = low[nod] = time;

    for(i=0; i<(int) a[nod].size(); i++) {

        child = a[nod][i];
        if(child != t[nod]) {
            if(!d[child]) {

                st.push( ii(nod, child) );
                t[child] = nod;
                DFS(child);

                if(low[child] >= d[nod])
                    biconex( nod, child );

                low[nod] = min( low[nod], low[child] );

            }
            else {
                low[nod] = min(low[nod], d[child]);
            }
        }
    }
}

int main(){

    int i, j, x, y;
    FILE *fin, *fout;
    fin = fopen("biconex.in", "r");
    fout = fopen("biconex.out", "w");

    fscanf(fin, "%d %d", &n, &m);
    for(i=1; i<=m; i++) {
        fscanf(fin, "%d %d", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
    }

    for(i=1; i<=n; i++) {
        if(!d[i])
            DFS(i);
    }

    for(i=1; i<=solsz; i++) {

        for(j=0; j<(int) sol[i].size(); j++)
            fprintf(fout, "%d ", sol[i][j]);
        fprintf(fout, "\n");
    }

    fclose(fin);
    fclose(fout);
    return 0;
}