Cod sursa(job #2608857)

Utilizator CristiPopaCristi Popa CristiPopa Data 1 mai 2020 20:12:34
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.62 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 100009

class Task {
 public:
    void solve() {
        read_input();
        get_result();
        print_output();
    }

 private:
    int n;
    int m;
    int time = 0;
    vector<int> nodes[NMAX];
    int found[NMAX];
    int low_link[NMAX];
    vector<unordered_set<int>> bcc;
    vector<pair<int, int>> edge_stack;

    void read_input() {
        ifstream fin("biconex.in");
        fin >> n >> m;
        for (int i = 0; i < m; ++i) {
            int x, y;
            fin >> x >> y;
            nodes[x].push_back(y);
            nodes[y].push_back(x);
        }
        fin.close();
    }

    void get_result() {
        vector<bool> visited(n + 1, false);
        for (int i = 1; i <= n; ++i) {
            if (!visited[i])
                dfs(i, visited, 0);
        }

    }

    void dfs(int node, vector<bool> &visited, int parent) {
        visited[node] = true;
        found[node] = time++;
        low_link[node] = found[node];
        for (int i : nodes[node]) {
            if (!visited[i]) {
                edge_stack.push_back({node, i});
                dfs(i, visited, node);
                low_link[node] = min(low_link[node], low_link[i]);
                if (low_link[i] >= found[node]) {
                    unordered_set<int> component;
                    pair<int, int> target = {node, i};
                    while (edge_stack.back() != target) {
                        component.insert(edge_stack.back().first);
                        component.insert(edge_stack.back().second);
                        edge_stack.pop_back();
                    }
                    edge_stack.pop_back();
                    component.insert(node);
                    component.insert(i);
                    bcc.push_back(component);
                }
            } else {
                if (i != parent) {
                    low_link[node] = min(low_link[node], low_link[i]);
                }
            }
        }
    }

    void print_output() {
        ofstream fout("biconex.out");
        int q = bcc.size();
        fout << q << endl;
        for (int i = 0; i < q; ++i) {
            for (int j : bcc[i])
                fout << j << ' ';
            fout << endl;
        }
        fout.close();
    }
};

// Please always keep this simple main function!
int main() {
    // Allocate a Task object on heap in order to be able to
    // declare huge static-allocated data structures inside the class.
    Task *task = new Task();
    task->solve();
    delete task;
    return 0;
}