Finding Bridges

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
691 B
4
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
class Bridge{
  vector<int> tin, fup;
  vector<bool>used;
  int timer = 0;
  Bridge(int n){
    used.resize(n + 1);
    tin.resize(n + 1);
    fup.resize(n + 1);
  }
  vector<pair<int, int> > bridges;

  void dfs(int v, int p = -1)
  {
    used[v] = true;
    tin[v] = fup[v] = timer++;
    // Change graph name to your own
    for (auto to : g[v])
    {
      if (to == p)
        continue;

      if (used[to])
        fup[v] = min(fup[v], tin[to]);
      else
      {
        dfs(to, v);
        fup[v] = min(fup[v], fup[to]);
        if (fup[to] > tin[v])
          bridges.pb({ v,to });
      }
    }
  }
}