説明

橋や関節点などを効率的に求める際に有効なアルゴリズム。

グラフをDFSして, ord[$idx$] := DFS で頂点に訪れた順番, low[$idx$] := 頂点 $idx$ からDFS木の葉方向の辺を $0$ 回以上, 後退辺を $1$ 回以下通って到達可能な頂点の $ord$ の最小値 を各頂点について求める。

ある頂点 $u$ が関節点であるとき, DFS木の根については子が $2$ つ以上, それ以外の頂点については 頂点 $u$ のある子 $v$ について ord[$u$] $\le$ low[$v$] を満たす。

ある辺 $(u, v)$ が橋であるとき, ord[$u$] $\lt$ low[$v$] を満たす。

計算量

  • $O(V)$

実装例

  • LowLink($g$):= グラフ $g$ で初期化する。
  • build():= グラフ $g$ に対する LowLink を構築する。構築後, articulation には関節点, bridge には橋が追加される。非連結でもOK。
template< typename G >
struct LowLink {
  const G &g;
  vector< int > used, ord, low;
  vector< int > articulation;
  vector< pair< int, int > > bridge;
 
  LowLink(const G &g) : g(g) {}
 
  int dfs(int idx, int k, int par) {
    used[idx] = true;
    ord[idx] = k++;
    low[idx] = ord[idx];
    bool is_articulation = false;
    int cnt = 0;
    for(auto &to : g[idx]) {
      if(!used[to]) {
        ++cnt;
        k = dfs(to, k, idx);
        low[idx] = min(low[idx], low[to]);
        is_articulation |= ~par && low[to] >= ord[idx];
        if(ord[idx] < low[to]) bridge.emplace_back(minmax(idx, (int) to));
      } else if(to != par) {
        low[idx] = min(low[idx], ord[to]);
      }
    }
    is_articulation |= par == -1 && cnt > 1;
    if(is_articulation) articulation.push_back(idx);
    return k;
  }
 
  virtual void build() {
    used.assign(g.size(), 0);
    ord.assign(g.size(), 0);
    low.assign(g.size(), 0);
    int k = 0;
    for(int i = 0; i < g.size(); i++) {
      if(!used[i]) k = dfs(i, k, -1);
    }
  }
};

検証

AOJ GRL_3_A 関節点

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_A"

#include "../../template/template.cpp"
#include "../template.cpp"

#include "../lowlink.cpp"

int main() {
  int V, E;
  scanf("%d %d", &V, &E);
  UnWeightedGraph g(V);
  for(int i = 0; i < E; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    g[x].push_back(y);
    g[y].push_back(x);
  }
  LowLink< UnWeightedGraph > lowlink(g);
  lowlink.build();
  sort(lowlink.articulation.begin(), lowlink.articulation.end());
  for(auto &v : lowlink.articulation) printf("%d\n", v);
}

AOJ GRL_3_B 橋

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B"

#include "../../template/template.cpp"
#include "../template.cpp"

#include "../lowlink.cpp"

int main() {
  int V, E;
  scanf("%d %d", &V, &E);
  UnWeightedGraph g(V);
  for(int i = 0; i < E; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    g[x].push_back(y);
    g[y].push_back(x);
  }
  LowLink< UnWeightedGraph > lowlink(g);
  lowlink.build();
  sort(lowlink.bridge.begin(), lowlink.bridge.end());
  for(auto &p : lowlink.bridge) printf("%d %d\n", p.first, p.second);
}