Wednesday, April 26, 2023

Bridge Tree [Updated Code]


#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
#define pii     pair<int, int>
 
template<const bool isWeighted> struct BridgeTree {
    int nodes;
    int edges;
    int dfsTime;
    vector<vector<int>> graph;
    vector<vector<vector<int>>> tree;
    vector<int> nodeCost;
    vector<vector<int>> edgeList;
    vector<bool> isBridge;
    vector<bool> visited;
    vector<int> arrivalTime;
    vector<int> par;
 
    BridgeTree(int n, int m) {
        nodes = n;
        edges = m;
        dfsTime = 0;
        int szn = n + 1;
        int szm = m + 1;
        int sznode = isWeighted ? 3 : 2;
        graph = vector<vector<int>>(szn);
        tree = vector<vector<vector<int>>>(szn);
        nodeCost = vector<int>(szn);
        edgeList = vector<vector<int>>(szm, vector<int>(sznode));
        isBridge = vector<bool>(szm);
        visited = vector<bool>(szn);
        arrivalTime = vector<int>(szn);
        par = vector<int>(szn);
        iota(par.begin(), par.end(), 0);
    }
    void readNodeCost() {
        for (int i = 1; i <= nodes; i++) {
            cin >> nodeCost[i];
        }
    }
    void readEdges() {
        for (int e = 1; e <= edges; e++) {
            for (int &x : edgeList[e]) {
                cin >> x;
            }
        }
    }
    int getAdjacent(int u, int e) {
        return edgeList[e][0] ^ edgeList[e][1] ^ u;
    }
    int findRep(int p) {
        return par[p] = (par[p] == p ? p : findRep(par[p]));
    }
    void marge(int u, int v) {
        int p = findRep(u);
        int q = findRep(v);
        par[q] = par[p];
    }
    int findBridge(int u, int edge = -1) {
        visited[u] = true;
        arrivalTime[u] = ++dfsTime;
        int minimumArrivalTime = arrivalTime[u];
        for (int nextEdge : graph[u]) {
            int v = getAdjacent(u, nextEdge);
            if (visited[v] == false) {
                minimumArrivalTime = min(minimumArrivalTime, findBridge(v, nextEdge));
            } else if (edge != -1) {
                minimumArrivalTime = min(minimumArrivalTime, arrivalTime[v]);
            }
        }
        if (minimumArrivalTime == arrivalTime[u] and edge != -1) {
            isBridge[edge] = true;
        } else if (edge != -1) {
            marge(edgeList[edge][0], edgeList[edge][1]);
        }
        return minimumArrivalTime;
    }
    void buildBridgeTree() {
        for (int i = 1; i <= nodes; i++) {
            if (visited[i] == false) {
                findBridge(i);
            }
        }
        for (int e = 1; e <= edges; e++) {
            int p = findRep(edgeList[e][0]);
            int q = findRep(edgeList[e][1]);
            if (p ^ q) {
                tree[p].emplace_back(q, isWeighted ? edgeList[e][2] : 0);
                tree[q].emplace_back(p, isWeighted ? edgeList[e][2] : 0);
            }
        }
    }
 
    // Implement solution methods from here
};
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = 1;
    if (FILEIO and fopen("in.txt", "r")) {
        freopen("in.txt", "r", stdin);
    }
 
    int n, m;
    cin >> n >> m;
    BridgeTree<false> brigeTree(n, m);
    brigeTree.readNodeCost();
    brigeTree.readEdges();
    brigeTree.buildBridgeTree();
}