Cod sursa(job #2756716)

Utilizator andreea.vasilescuAndreea Vasilescu andreea.vasilescu Data 2 iunie 2021 17:13:56
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.57 kb

#include<cstdio>
#include<vector>

using namespace std;

const int N = 100005;

int n, m, nr, nivel[N], nivelmin[N], biconex, muchiex[N], muchiey[N];

vector <int> v[N], mat[N];

bool marcat[N];

//Se dă un graf neorientat G = (V, E). Un graf se numeşte graf biconex dacă nu are puncte de articulaţie.
// Un nod se numeşte punct de articulaţie dacă subgraful obţinut prin eliminarea nodului şi a muchiilor incidente cu acesta nu mai este conex.
// O componentă biconexă a unui graf este un subgraf biconex maximal cu această proprietate.

void citire() {
    scanf("%d%d", &n, &m);

    int x, y;

    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &x, &y);
//  muchii bidirectionale (graful e neorientat )
        v[x].push_back(y);
        v[y].push_back(x);
    }

}

void dfs(int nod) {
    marcat[nod] = true;
    nivelmin[nod] = nivel[nod];
// iterator : parcurge efectiv elementele
// in *it se va gasi elementul din vector ( adica vecinul )
//  in loc v[nod][i] <=> *it
    for (vector <int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it)
//        daca vecinul respectiv nu a fost marcat
        if (!marcat[*it]) {
//            ii spun ca il pun pe urmatorul nivel
            nivel[*it] = nivel[nod] + 1;
//  muchiex : retine nodul la care sunt
//  muchiey : retine vecinul

            muchiex[++nr] = nod;
            muchiey[nr] = *it;
//  apelez recursiv dfs de vecin
            dfs(*it);
//  pornesc din radacina si tot cobor,
//  daca eu cumva coborand ajung sa am un copil care are o adancime mai sus decat tatal,
//  inseamna ca a fost ciclu, deci este critica
//  daca nu s-a inchis un ciclu
//  if spune ca este mai jos decat nodul curent => ne aflam pe o muchie critica
            if (nivelmin[*it] >= nivel[nod]) {
//                adaug o noua componenta biconexa
                ++biconex;
                
                while (muchiex[nr] != nod || muchiey[nr] != *it)
                    mat[biconex].push_back(muchiey[nr--]);

                mat[biconex].push_back(nod);
                mat[biconex].push_back(*it);
                --nr;
            }

            nivelmin[nod] = min(nivelmin[nod], nivelmin[*it]);
        }
        else
            nivelmin[nod] = min(nivelmin[nod], nivel[*it]);
}

void afisare() {
    printf("%d\n", biconex);
    for (int i = 1; i <= biconex; ++i, printf("\n"))
        for (vector <int>::iterator it = mat[i].begin(); it != mat[i].end(); ++it)
            printf("%d ", *it);
}

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

    citire();

    dfs(1);

    afisare();

    return 0;
}