Cod sursa(job #2668116)

Utilizator dianapingu1Diana Vasiliu dianapingu1 Data 4 noiembrie 2020 15:07:50
Problema Componente biconexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.25 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace  std;

const int NMAX = 100005;
const int INF = 1000000000;

vector<int> muchii[NMAX];
vector<int> biconexe[NMAX];
int viz[NMAX];
int nivel[NMAX];
int inaltime[NMAX];
bool critic[NMAX];
int dfs_sons[NMAX];
int num_bic;

void dfs_critic(int nod) {
    viz[nod] = 1;

    for (const auto &vec : muchii[nod]) {
        if (!viz[vec]) {
            nivel[vec] = nivel[nod] + 1;
            dfs_sons[nod]++;

            dfs_critic(vec);

            if (inaltime[vec] >= nivel[nod]) {
                critic[nod] = true;
            }
            inaltime[nod] = min(inaltime[nod], inaltime[vec]);
        }
        else {
            inaltime[nod] = min(inaltime[nod], nivel[vec]);
        }
    }
}

void dfs_biconexe(int nod, int index);

void split_biconexe(int nod) {
    viz[nod] = 1;
    for (auto &vec : muchii[nod]) {
        if (viz[vec]) {
            continue;
        }

        biconexe[++num_bic].push_back(nod);
        if (critic[vec]) {
            biconexe[num_bic].push_back(vec);
            split_biconexe(vec);
        }
        else {
            dfs_biconexe(vec, num_bic);
        }
    }
}

void dfs_biconexe(int nod, int index) {
    viz[nod] = 1;
    biconexe[index].push_back(nod);
    for (auto &vec : muchii[nod]) {
        if (viz[vec]) {
            continue;
        }
        if (critic[vec]) {
            biconexe[index].push_back(vec);
            split_biconexe(vec);
        }
        else {
            dfs_biconexe(vec, index);
        }
    }
}

int main() {

    ifstream fin("biconex.in");
    ofstream fout("biconex.out");

    int n,m,a,b;
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        fin >> a >> b;
        muchii[a].push_back(b);
        muchii[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) {
        inaltime[i] = INF;
    }

    dfs_critic(1);

    critic[1] = (dfs_sons[1] > 1);

    for (auto &v : viz) {
        v = 0;
    }

    for(int i = 1; i <= n; i++) {
        if(critic[i]) {
            split_biconexe(i);
            break;
        }
    }

    fout << num_bic << "\n";
    for (int i = 1; i <= num_bic; i++) {
        for (auto &elem : biconexe[i]) {
            fout << elem << " ";
        }
        fout << "\n";
    }

    return 0;
}