Find bridges in graph (incomplete)

bridges.cpp

/* Copyright 2016 Rafael Rendón Pablo <[email protected]> */
// region Template
#include <bits/stdc++.h>
using namespace std;
typedef long long           int64;
typedef unsigned long long  uint64;
const double kEps   = 10e-8;
const int kMax      = 1000;
const int kInf      = 1 << 30;
const int kRedEdge = 1;
const int kGreenEdge = 2;
// endregion
struct Node {
    int post_order;
    int number_of_descendants;
    int lowest_post_order;
    int highest_post_order;
    map<int, int> neighbors;
    int& operator[](int i) {
        return neighbors[i];
    }

    bool contains(int v) {
        return neighbors.count(v) == 1;
    }
};


typedef vector<vector<int>> Graph;
typedef vector<Node> Tree;

// region DisjointSet
class DisjointSet {
public:
    DisjointSet() { }
    DisjointSet(int size) {
        id_.resize(max(1, size));
        size_.resize(max(1, size));
        iota(begin(id_), end(id_), 0);
    }

    bool connected(int u, int v) {
        return root(u) == root(v);
    }

    void connect(int u, int v) {
        u = root(u);
        v = root(v);
        if (size_[u] < size_[v]) {
            id_[u] = v;
            size_[v] += size_[u];
        } else {
            id_[v] = u;
            size_[u] += size_[v];
        }
    }
private:
    vector<int> id_;
    vector<int> size_;
    int root(int u) {
        while (u != id_[u]) {
            u = id_[u];
        }
        return u;
    }
};
// endregion

void BuildTree(int u, Graph& graph, Tree& tree, DisjointSet& ds, int& post_order) {
    for (int v : graph[u]) {
        if (ds.connected(u, v)) {
            if (tree[v].contains(u) == 0) {
                tree[u][v] = kRedEdge;
                tree[v][u] = kRedEdge;
            }
        } else {
            tree[u][v] = kGreenEdge;
            ds.connect(u, v);
            BuildTree(v, graph, tree, ds, post_order);
        }
    }
    tree[u].lowest_post_order = post_order;
    tree[u].highest_post_order = post_order;
    tree[u].post_order = post_order++;
}

void LabelTree(Tree& tree, int u) {
    tree[u].number_of_descendants = 0;
    for (auto e : tree[u].neighbors) {
        int v = e.first;
        int t = e.second;
        if (t == kGreenEdge) {
            LabelTree(tree, v);
            tree[u].number_of_descendants += tree[v].number_of_descendants;
        }
        tree[u].lowest_post_order = min(tree[u].lowest_post_order, tree[v].lowest_post_order);
        tree[u].highest_post_order = max(tree[u].highest_post_order, tree[v].highest_post_order);
    }
    tree[u].number_of_descendants++;
}

void FindBridges(Tree& tree, int u, vector<pair<int, int>>& bridges) {
    for (auto e : tree[u].neighbors) {
        int v = e.first;
        int t = e.second;
        if (t == kRedEdge) {
            continue;
        }
        int po = tree[v].post_order;
        int nod = tree[v].number_of_descendants;
        int lpo = tree[v].lowest_post_order;
        int hpo = tree[v].highest_post_order;
        if (hpo <= po && lpo > (po - nod)) {
            bridges.push_back({u, v});
        }
        FindBridges(tree, e.first, bridges);
    }
}

vector<pair<int, int>> Tarjan(Graph graph) {
    Tree tree(graph.size());
    DisjointSet ds(graph.size());
    int post_order = 1;
    BuildTree(0, graph, tree, ds, post_order);
    LabelTree(tree, 0);
    vector<pair<int, int>> bridges;
    FindBridges(tree, 0, bridges);
    return bridges;
}

int main() {
    int n, m;
    Graph graph;
    cin >> n >> m;
    graph.resize(n);
    for (int _ = 0; _ < m; _++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    auto bridges = Tarjan(graph);
    for (auto e : bridges) {
        cout << e.first << " " << e.second << endl;
    }
    return EXIT_SUCCESS;
}