Cod sursa(job #2677388)

Utilizator marius004scarlat marius marius004 Data 26 noiembrie 2020 14:29:20
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.07 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>

//#define f cin
//#define g cout

using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

const int NMAX = 100'001;

int N, M, low[NMAX], level[NMAX], biconnectedComponentsCnt;
vector < int > G[NMAX];
bitset < NMAX > V;
stack < int > Stack;
vector < int > biconnectedComponents[NMAX]; // pot fi maxim NMAX componente biconexe(cred)

void dfs(const int& node, const int& parent, const int& l) {

    V[node] = 1;
    level[node] = low[node] = l;
    Stack.push(node);

    for(const int& neighbor : G[node]) {

        if(neighbor == parent) // nu vrem sa ne intoarcem de unde am venit
            continue;

        if(V[neighbor] == 1) { // muchia currenta este o muchie de intoarcere
            low[node] = min(low[node], level[neighbor]); // aici am pus level[neighbor] pt ca muchia (node, neighbour)
            // este muchie de intoarcere, caruia ii stim deja valoarea. BE AWARE: NU PUNE low[neighbor] pt ca o data ce
            // muchia de intoarcere este folosita nu mai pot sa urc in "DFS TREE"
            continue;
        }

        dfs(neighbor, node, l + 1);
        low[node] = min(low[node], low[neighbor]);

        if(low[neighbor] >= level[node]) { // daca "node" formeaza o noua componta biconexa
            biconnectedComponentsCnt++;
            int stackTopValue{};

            do {
                stackTopValue = Stack.top();
                Stack.pop();
                biconnectedComponents[biconnectedComponentsCnt].emplace_back(stackTopValue);
            } while(stackTopValue != neighbor);

            biconnectedComponents[biconnectedComponentsCnt].emplace_back(node);
        }
    }
}

int main() {

    f >> N >> M;

    while(M--) {

        int u, v;
        f >> u >> v;

        G[u].push_back(v);
        G[v].push_back(u);
    }

    dfs(1, 0, 1);

    g << biconnectedComponentsCnt << "\n";
    for(int i = 1;i <= biconnectedComponentsCnt;++i, g << '\n') {
        for(const auto& it : biconnectedComponents[i])
            g << it << ' ';
    }

    return 0;
}