Cod sursa(job #1831279)

Utilizator DanielRusuDaniel Rusu DanielRusu Data 17 decembrie 2016 19:00:42
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.38 kb
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

#define DIM 100005

vector <vector <int> > G, Rez;
int tmp = 1, N, M, x, y;
int Timp[DIM], Best[DIM], viz[DIM], St[DIM], eSt[DIM];

void DF(int nod, int prev);

int main() {
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);

    scanf("%d %d\n", &N, &M);

    G.resize(N + 2);

    for(int i = 1; i <= M; ++i) {
        scanf("%d %d\n", &x, &y);

        G[x].push_back(y);
        G[y].push_back(x);
    }

    for(int i = 1; i <= N; ++i) {
        if(!viz[i]) {
            DF(i, 0);
        }
    }

    cout << Rez.size() << '\n';

    for(unsigned int c = 0; c < Rez.size(); ++c) {
        for(unsigned int z = 0; z < Rez[c].size(); ++z) {
            cout << Rez[c][z] << ' ';
        }

        cout << '\n';
    }

    return 0;
}

void DF(int nod, int prev) {
    viz[nod] = 1;
    St[++St[0]] = nod;
    eSt[nod] = 1;

    Timp[nod] = tmp;
    Best[nod] = tmp++;

    for(unsigned int z = 0; z < G[nod].size(); ++z) {
        if(prev == G[nod][z]) continue;
        if(!viz[G[nod][z]]) {
            DF(G[nod][z], nod);
            if(Best[G[nod][z]] == Timp[G[nod][z]]) {
                vector <int> x;

                x.push_back(nod);
                x.push_back(G[nod][z]);

                Rez.push_back(x);
            }
            if(Timp[nod] == Best[G[nod][z]]) {
                vector <int> x;

                while(St[St[0]] != nod) {
                    x.push_back(St[St[0]]);
                    eSt[St[St[0]]] = 0;
                    --St[0];
                }

                x.push_back(nod);

                Rez.push_back(x);

//                eSt[nod] = 0;
//                --St[0];
            }
            Best[nod] = min(Best[nod], Best[G[nod][z]]);
        }
        else {
            if(eSt[G[nod][z]] == 1) {
                Best[nod] = min(Best[nod], Best[G[nod][z]]);
            }
        }
    }

    if(Best[nod] == Timp[nod]) {
//        vector <int> x;
//
//        while(St[St[0]] != nod) {
//            x.push_back(St[St[0]]);
//            eSt[St[St[0]]] = 0;
//            --St[0];
//        }
//
//        x.push_back(nod);
//
//        Rez.push_back(x);
//
//        eSt[nod] = 0;
//        --St[0];
//    }

        --St[0];
        eSt[nod] = 0;
    }
}