Cod sursa(job #2897011)

Utilizator mihnea.tTudor Mihnea mihnea.t Data 2 mai 2022 00:59:11
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.44 kb
#include <bits/stdc++.h>

#define INF  ((int)1e9)
#define NMAX ((int)1e5)

using namespace std;

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

int n, m;
vector<int> adj[NMAX + 1];
vector<unordered_set<int>> all_bccs;

void dfs(int node, vector<int> &parent, int &timestamp, vector<int> &found, vector<int> &low_link,
        stack<pair<int, int>> &edges) {
    found[node] = ++timestamp;
    low_link[node] = found[node];

    int children = 0;
    for (auto it = adj[node].begin(); it != adj[node].end(); ++it) {
        int next_node = *it;
        if (parent[next_node] != -1) {
            if (next_node != parent[node]) {
                low_link[node] = min(low_link[node], found[next_node]);
            }

            continue;
        }

        parent[next_node] = node;
        ++children;

        edges.push({node, next_node});
        dfs(next_node, parent, timestamp, found, low_link, edges);

        low_link[node] = min(low_link[node], low_link[next_node]);

        if (low_link[next_node] >= found[node]) {
            unordered_set<int> bcc_nodes;
            while (true) {
                pair<int, int> curr_edge = edges.top();
                edges.pop();

                bcc_nodes.insert(curr_edge.first);
                bcc_nodes.insert(curr_edge.second);

                if (curr_edge == make_pair(node, next_node)) {
                    break;
                }
            }

            all_bccs.push_back(bcc_nodes);
        }
    }
}

void tarjan_bcc(vector<int> &parent, vector<int> &found, vector<int> &low_link) {
    for (int i = 0; i <= n; ++i) {
        parent[i] = -1;
        found[i] = INF;
        low_link[i] = INF;
    }

    stack<pair<int, int>> edges;
    int timestamp = 0;
    for (int i = 1; i <= n; ++i) {
        if (parent[i] == -1) {
            parent[i] = i;

            dfs(i, parent, timestamp, found, low_link, edges);
        }
    }
}

int main(void) {
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int src, dest;
        fin >> src >> dest;
        adj[src].push_back(dest);
        adj[dest].push_back(src);
    }

    vector<int> parent(n + 1);
    vector<int> found(n + 1);
    vector<int> low_link(n + 1);

    tarjan_bcc(parent, found, low_link);

    fout << all_bccs.size() << "\n";

    for (size_t i = 0; i < all_bccs.size(); ++i) {
        for (auto it = all_bccs[i].begin(); it != all_bccs[i].end(); ++it) {
            fout << *it << " ";
        }

        fout << "\n";
    }

    return 0;
}