Finding articulation points

 avatar
unknown
c_cpp
3 years ago
1.1 kB
6
Indexable
class ArticulationPoints
{
public:
  vector<int> tin, mn, cutVertices;
  vector<bool> used;
  int timer;
  ArticulationPoints(int MAXN){
    timer = 0;
    used.resize(MAXN);
    mn.resize(MAXN);
    tin.resize(MAXN);
  }
  

  void dfs(int v, int par = -1) {
      used[v] = true;
      timer++;
      tin[v] = timer;
      mn[v] = tin[v];

      int childNum = 0;
      bool isCutVertex = false;
      // Change the graph name to your own and create it
      for (int i = 0; i < (int) g[v].size(); i++) {
          int to = g[v][i];
          if (!used[to]) {
              childNum++;
              dfs(to, v);
              if (par != -1 && mn[to] >= tin[v] && !isCutVertex) {
                  isCutVertex = true;
                  cutVertices.push_back(v);
              }
              mn[v] = min(mn[v], mn[to]);
          }
          else if (to != par) {
              mn[v] = min(mn[v], tin[to]);
          }
      }

      if (par == -1 && childNum > 1)
          cutVertices.push_back(v);
  }
};
Editor is loading...