code/graphs/articulationPoints.cc

View this file on GitHub
Last update: 2020-10-28 19:21:59+01:00

Depends on

code/template.cc

Verified with

tests/aoj/articulation_points.articulation_points.test.cpp

Code

#include "../template.hh"
vi dfsNum, low;
int dfsCounter = 0;
vvi adj;
int artiDfs(int v, vi& a, int p = -1) {
  dfsNum[v] = low[v] = dfsCounter++;
  int children = 0;
  bool aP = false;
  for (int u : adj[v]) {
    if (dfsNum[u] == -1) {
      ckmin(low[v], artiDfs(u, a, v));
      if (low[u] >= dfsNum[v] && p != -1 && !aP) {
        a.pb(v);
        aP = true;
      }
      children++;
    } else if (u != p)
      ckmin(low[v], dfsNum[u]);
  }
  if (p == -1 && children > 1) a.pb(v);
  return low[v];
}
vi findArtiPoints() {
  dfsNum.assign(SZ(adj), -1);
  low.assign(SZ(adj), -1);
  dfsCounter = 0;
  vi res;
  F0R (v, SZ(adj))
    if (dfsNum[v] == -1) artiDfs(v, res);
  return res;
}

#line 1 "code/template.cc"
// this line is here for a reason
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define endl '\n'
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(x) (int)(x).size()
#define FOR(a, b, c) for (auto a = (b); (a) < (c); ++(a))
#define F0R(a, b) FOR (a, 0, (b))
template <typename T>
bool ckmin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <typename T>
bool ckmax(T& a, const T& b) { return a < b ? a = b, true : false; }
#ifndef DEBUG
#define DEBUG 0
#endif
#define dout if (DEBUG) cerr
#define dvar(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#line 2 "code/graphs/articulationPoints.cc"
vi dfsNum, low;
int dfsCounter = 0;
vvi adj;
int artiDfs(int v, vi& a, int p = -1) {
  dfsNum[v] = low[v] = dfsCounter++;
  int children = 0;
  bool aP = false;
  for (int u : adj[v]) {
    if (dfsNum[u] == -1) {
      ckmin(low[v], artiDfs(u, a, v));
      if (low[u] >= dfsNum[v] && p != -1 && !aP) {
        a.pb(v);
        aP = true;
      }
      children++;
    } else if (u != p)
      ckmin(low[v], dfsNum[u]);
  }
  if (p == -1 && children > 1) a.pb(v);
  return low[v];
}
vi findArtiPoints() {
  dfsNum.assign(SZ(adj), -1);
  low.assign(SZ(adj), -1);
  dfsCounter = 0;
  vi res;
  F0R (v, SZ(adj))
    if (dfsNum[v] == -1) artiDfs(v, res);
  return res;
}