Cod sursa(job #454051)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 11 mai 2010 17:39:44
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.37 kb
#include <stdio.h>
#include <set>
#include <vector>
#include <utility>

using namespace std;

#define maxN    100100
#define maxM    200100
#define oo      100100
#define ROOT    1

int N, M, Nr, cate_ramase;
int low[maxN], nivel[maxN];
int Biconexa[maxM];
vector <int> G[maxN], Ind[maxN], ind;
vector < pair <int, int> > stack;
set <int> Sol_vec[maxN];
char art_point[maxN], viz[maxN];

void baga_marfa () {
    Sol_vec[Nr].insert(stack.back().first);                 // adaug cele 2 noduri la biconexa, in caz ca mai sunt deja nu apar de 2 ori
    Sol_vec[Nr].insert(stack.back().second);
    Biconexa[ind.back()] = Nr;                              // tin minte din ce biconexa face parte muchia
    stack.pop_back();                                       // scot ultima muchie din stiva
    ind.pop_back();
}

void df (int nod, int parinte) {
    int niv_min = oo;                               // nivelul minim la care pot ajunge din descendenti + muchie de intoarcere

    viz[nod] = 1;                                   // marchez nodul ca vizitat
    nivel[nod] = nivel[parinte] + 1;                // nivelul nodului este nivelul parintelui + 1
    cate_ramase --;                                 // am mai vizitat un nod, scad numarul celor nevizitate
    low[nod] = nivel[nod];                          // momentan nivelul minim la care se poate ajunge din nodul curent in sus este nivelul lui

    for (vector <int> :: iterator it = G[nod].begin(); it != G[nod].end(); ++ it) {     // parcurg vecinii
        if (*it == parinte || (viz[*it] && nivel[*it] > nivel[nod]))     continue;      // in caz ca e parintele ma opresc

        stack.push_back(make_pair(nod, *it));                                           // bag muchia curenta in stiva
        ind.push_back(Ind[nod][it - G[nod].begin()]);                                   // si indicele ei, o sa ma ajute mai tarziu la reconstructie

        if (viz[*it]) {                                                                 // daca a mai fost vizitat, e muchie de intoarcere
            low[nod] = min(low[nod], nivel[*it]);                                       // vad daca pot ajunge mai sus decat pana acum
        } else {
            df(*it, nod);                                                               // ma duc pe muchia de dus
            niv_min = min(niv_min, low[*it]);                                           // modific corespunzator nivelul minim la care se poate ajunge din fii

            if (low[*it] >= nivel[nod] && nod != ROOT) {                                // daca toti descendentii lui ajung maxim pana la nivelul lui
                art_point[nod] = 1;                                                     // e punct de articulatie
                ++ Nr;                                                                  // apare o noua biconexa

                for (; stack.back() != make_pair(nod, *it); baga_marfa());
                baga_marfa();                                                           // scot din stiva pana ajung la muchia curenta, inclusiv ea.
            }
        }

        if (nod == ROOT && cate_ramase) {                                               // ma uit daca nu e nodul 1 punct de articulatie
            art_point[nod] = 1;
            ++ Nr;

            for (; stack.back() != make_pair(nod, *it); baga_marfa());                  // adaug biconexa
            baga_marfa();
        }
    }

    low[nod] = min(low[nod], niv_min);                                                  // marchez nivelul minim la care poate ajunge
}

int main () {
    int i, a, b;

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

    scanf("%d%d", &N, &M);  // citesc numarul de noduri si numarul de muchii

    for (i = 1; i <= M; ++ i) {
        scanf("%d%d", &a, &b);      // citesc muchiile

        G[a].push_back(b);          // construiesc graful
        G[b].push_back(a);

        Ind[a].push_back(i);        // tin minte indicii muchiilor
        Ind[b].push_back(i);
    }

    cate_ramase = N;                // cate noduri nu au fost vizitate
    df(ROOT, 0);                       // parcurg in adancime

    if (stack.size()) {
        ++ Nr;
        for (; stack.size(); baga_marfa());
    }

    printf("%d\n", Nr);

    for (i = 1; i <= Nr; ++ i) {
        for (set <int> :: iterator it = Sol_vec[i].begin(); it != Sol_vec[i].end(); ++ it)
            printf("%d ", *it);
        puts("");
    }
}