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();
} 

  

[Codeforces] E. We Need More Bosses

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E. We Need More Bosses
Source            : Codeforces
Category          : Graph Theory
Algorithm         : Bridge Tree, Tree Diameter
Verdict           : Accepted

 
#include "bits/stdc++.h"
 
using namespace std;
 
#define FI              freopen("in.txt", "r", stdin)
#define FO              freopen("out.txt", "w", stdout)
#define FAST            ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
 
#define FOR(i, n)       for (int i = 1; i <= n; i++)
#define For(i, n)       for (int i = 0; i < n; i++)
#define ROF(i, n)       for (int i = n; i >= 1; i--)
#define Rof(i, n)       for (int i = n-1; i >= 0; i--)
#define FORI(i, n)      for (auto i : n)
#define eb              emplace_back
#define pb              push_back
#define ll              long long
#define ull             unsigned long long
#define vi              vector <int>
#define vl              vector <ll>
#define All(a)          a.begin(), a.end()
#define endl            '\n'
#define sz(a)           a.size()
#define lb              lower_bound
#define mod             1000000007
 
inline int setbit(int mask, int pos)      { return mask |= (1 << pos); }
inline int resetbit(int mask, int pos)    { return mask &= ~(1 << pos); }
inline int togglebit(int mask, int pos)   { return mask ^= (1 << pos); }
inline bool checkbit(int mask, int pos)   { return (bool)(mask & (1 << pos)); }
 
static const int maxn = 3e5 + 5;
static const int logn = 18;
 
struct node
{
      int v, e;
      node(int v = 0, int e = 0) : v(v), e(e) {}
};
 
vector <node> graph[maxn];
bool isBridge[maxn], vis[maxn];
int timer, dis[maxn], low[maxn];
 
inline void findBridge(int u = 1, int p = -1)
{
      vis[u] = 1;
      dis[u] = low[u] = ++timer;
      for (node it : graph[u])
      {
            int v = it.v;
            int e = it.e;
            if (v == p) continue;
            if (!vis[v])
            {
                  findBridge(v, u);
                  low[u] = min(low[u], low[v]);
                  if (dis[u] < low[v]) isBridge[e] = 1;
            }
            else
            {
                  low[u] = min(low[u], dis[v]);
            }
      }
}
 
int compo, compo_num[maxn];
bool used[maxn];
vector <int> tree[maxn];
 
inline void makeTree(int src)
{
      used[src] = 1;
      int cur_compo = compo;
      compo_num[src] = cur_compo;
      queue <int> PQ;
      PQ.emplace(src);
      while (!PQ.empty())
      {
            int u = PQ.front(); PQ.pop();
            for (node it : graph[u])
            {
                  int v = it.v;
                  int e = it.e;
                  if (used[v]) continue;
                  if (isBridge[e])
                  {
                        compo++;
                        tree[cur_compo].eb(compo);
                        tree[compo].eb(cur_compo);
                        makeTree(v);
                  }
                  else
                  {
                        PQ.emplace(v);
                        used[v] = 1;
                        compo_num[v] = cur_compo;
                  }
            }
      }
}
 
int maxDis, maxDisNode;
 
inline void dfs(int u, int p = -1, int level = 0)
{
      if (level > maxDis) maxDis = level, maxDisNode = u;
      for (int v : tree[u])
      {
            if (v == p) continue;
            dfs(v, u, level+1);
      }
}
 
int main()
{
      int tnode, tedge;
      cin >> tnode >> tedge;
      FOR(e, tedge)
      {
            int u, v;
            cin >> u >> v;
            graph[u].eb(v, e);
            graph[v].eb(u, e);
      }
      compo = 1;
      findBridge(1);
      makeTree(1);
      maxDis = -1, maxDisNode = -1;
      dfs(1);
      maxDis = -1;
      dfs(maxDisNode);
      cout << maxDis;
}

[Gym] H. Capital City

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : H. Capital City
                    2015 ACM Arabella Collegiate Programming Contest
Source            : Gym
Category          : Graph Theory, Dynamic Programing
Algorithm         : Bridge Tree, DP on Tree
Verdict           : Accepted

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
static const int maxn = 3e5 + 5;
 
struct node
{
    int v, e;
    ll w;
    node() {}
    node(int vv, int ee, ll ww) : v(vv), e(ee), w(ww) {}
};
 
vector <node> G[maxn];
bool isBridge[maxn], vis[maxn];
int timer, dis[maxn], low[maxn];
 
inline void findBridge(int u, int p = -1)
{
    vis[u] = 1;
    dis[u] = low[u] = timer++;
    for (auto &it : G[u])
    {
        int v = it.v;
        int e = it.e;
        if (v == p) continue;
        if (!vis[v])
        {
            findBridge(v, u);
            low[u] = min(low[u], low[v]);
            if (dis[u] < low[v]) isBridge[e] = 1;
        }
        else
        {
            low[u] = min(low[u], dis[v]);
        }
    }
}
 
int compo;
bool used[maxn];
int compo_num[maxn];
set <int> component[maxn];
vector <node> tree[maxn];
 
inline void bridgeTree(int src)
{
    used[src] = 1;
    int cur_compo = compo;
    compo_num[src] = cur_compo;
    component[cur_compo].insert(src);
    queue <int> PQ;
    PQ.push(src);
    while (!PQ.empty())
    {
        int u = PQ.front(); PQ.pop();
        for (auto &it : G[u])
        {
            int v = it.v;
            int e = it.e;
            ll w = it.w;
            if (used[v]) continue;
            if (isBridge[e])
            {
                compo++;
                tree[cur_compo].push_back(node(compo, e, w));
                tree[compo].push_back(node(cur_compo, e, w));
                bridgeTree(v);
            }
            else
            {
                PQ.push(v);
                used[v] = 1;
                compo_num[v] = cur_compo;
                component[cur_compo].insert(v);
            }
        }
    }
}
 
ll in[maxn], out[maxn];
 
inline void dfs(int u, int p)
{
    in[u] = 0;
    for (auto &it : tree[u])
    {
        int v = it.v;
        ll w = it.w;
        if (v == p) continue;
        dfs(v, u);
        in[u] = max(in[u], w + in[v]);
    }
}
 
inline void dfs2(int u, int p)
{
    ll mx1 = -1;
    ll mx2 = -1;
    for (auto &it : tree[u])
    {
        int v = it.v;
        ll w = it.w;
        if (v == p) continue;
        if (in[v]+w >= mx1)
        {
            mx2 = mx1;
            mx1 = w + in[v];
        }
        else if (in[v]+w > mx2)
        {
            mx2 = w + in[v];
        }
    }
    for (auto &it : tree[u])
    {
        int v = it.v;
        ll w = it.w;
        if (v == p) continue;
        ll use = mx1;
        if (in[v]+w == mx1) use = mx2;
        out[v] = max(w+out[u], w+use);
        dfs2(v, u);
    }
}
 
inline void init()
{
    timer = 1;
    compo = 1;
    for (int i = 0; i < maxn; i++)
    {
        dis[i] = 0;
        low[i] = 0;
        isBridge[i] = 0;
        vis[i] = 0;
        used[i] = 0;
        compo_num[i] = -1;
        G[i].clear();
        tree[i].clear();
        in[i] = 0;
        out[i] = 0;
        component[i].clear();
    }
}
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    int tc;
    scanf("%d", &tc);
    for (int tcase = 1; tcase <= tc; tcase++)
    {
        init();
        int tNode, tEdge;
        scanf("%d %d", &tNode, &tEdge);
        int root = 1;
        for (int e = 1; e <= tEdge; e++)
        {
            int u, v;
            ll w;
            scanf("%d %d %lld", &u, &v, &w);
            assert(u != v);
            root = max(root, max(u, v));
            G[u].push_back(node(v, e, w));
            G[v].push_back(node(u, e, w));
        }
        findBridge(root);
        bridgeTree(root);
        dfs(1, -1);
        dfs2(1, -1);
        ll maxCost = 1e15 + 5;
        int city = tNode + 1;
        for (int i = 1; i <= compo; i++)
        {
            ll cc = max(in[i], out[i]);
            if (cc < maxCost)
            {
                maxCost = cc;
                city = *component[i].begin();
            }
            else if (cc == maxCost)
            {
                city = min(city, *component[i].begin());
            }
        }
        printf("%d %lld\n", city, maxCost);
    }
}