Cod sursa(job #2606513)

Utilizator CosminBanicaBanica Cosmin CosminBanica Data 27 aprilie 2020 21:50:22
Problema Componente biconexe Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.37 kb
#include <bits/stdc++.h>
using namespace std;
#define NMAX 100009
#define edge pair<int, int>

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

  private:
    vector<int> adj[NMAX];
    vector<int> found;
    vector<int> low_link;
    vector<int> cut_vertex;
    vector<set<int>> bcc;
    vector<edge> critical_edges;
    stack<edge> sc;
    vector<int> is_cv;
    vector<int> parent;
    int n, m;

    void read_input() {
        ifstream fin("biconex.in");
        fin >> n >> m;

        found = vector<int>(n + 1, -1);
        low_link = vector<int>(n + 1, 0);
        parent = vector<int>(n + 1, 0);
        is_cv = vector<int>(n + 1, 0);

        for (int i = 1; i <= m; ++i) {
            int x, y;
            fin >> x >> y;

            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        fin.close();
    }

    void get_result() {
        int current_start = 0;
        
        for (int i = 1; i <= n; ++i) {
            if (found[i] == -1) {
                parent[i] = 0;
                tarjan(i, current_start);
            }
        }
    }

    void tarjan(int node, int &current_start) {
        ++current_start;

        found[node] = current_start;
        low_link[node] = current_start;

        int children = 0;

        for (int neighbour : adj[node]) {
            if (found[neighbour] == -1) {
                parent[neighbour] = node;
                ++children;
                sc.push(edge(node, neighbour));

                tarjan(neighbour, current_start);
                low_link[node] = min(low_link[node], low_link[neighbour]);
            
                if (low_link[neighbour] >= found[node]) {
                    if (parent[node] != 0) {
                        if (!is_cv[node]) {
                            is_cv[node] = 1;
                            cut_vertex.push_back(node);
                        }
                    }

                    get_bcc(edge(node, neighbour));
                }

                if (low_link[neighbour] > found[node]) {
                    critical_edges.push_back(edge(node, neighbour));
                }
            } else {
                if (neighbour != parent[node]) {
                    low_link[node] = min(low_link[node], found[neighbour]);
                }
            }
        }

        if (parent[node] == 0 && children >= 2) {
            if (!is_cv[node]) {
                is_cv[node] = 1;
                cut_vertex.push_back(node);
            }
        }
    }

    void get_bcc(edge target_edge) {
        set<int> current_bcc;
        edge current_edge = edge(-1, -1);

        while (current_edge != target_edge) {
            current_edge = sc.top();
            sc.pop();

            current_bcc.insert(current_edge.first);
            current_bcc.insert(current_edge.second);
        }

        bcc.push_back(current_bcc);
    }

    void print_output() {
        ofstream fout("biconex.out");
        fout << bcc.size() << "\n";
        for (set<int> comp : bcc) {
            for (int el : comp) {
                fout << el << " ";
            }
            fout << "\n";
        }
        fout.close();
    }
};

int main() {
    Task *task = new Task();
    task->solve();
    delete task;

    return 0;
}