関節点・橋の定義

• 無向グラフに関する概念
• 関節点: その頂点を取り除くと連結成分が増える頂点
• 橋: その辺を取り除くと連結成分が増える辺

参考記事

• algo-logic
  • グラフにおける関節点(Articulation Points)を検出するアルゴリズム | アルゴリズムロジック
  • グラフにおける橋(bridge)を検出するアルゴリズム | アルゴリズムロジック
• DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【後編】 #AtCoder - Qiita
• グラフ探索アルゴリズム とその応用 (JOI のスライド？)

関節点・橋のアルゴリズムにでてくる概念

• 後退辺

  • DFS で通らなかった辺 （DFS 木に含まれない辺のこと）

• lowlink

  • 頂点uの行きがけ順を ord[u] で表す
  • 頂点uのlowlink low[u] は以下の方法でたどり着ける頂点の中での ord の最小値である
    1. DFS木の辺を進む (0回以上)
    2. 後退辺を進む (1回まで)

  

橋・関節点の条件

• 橋の条件

  • 辺 (u, v) が橋 ⟺ ord[u] < low[v]

  

• 関節点の条件

  • 頂点 u が関節点 ⟺ ① or ②
    • ① u がDFS tree の根で、子が2つ以上存在
    • ② u が DFS tree の根ではなくて、u の DFS tree のある子 v について ord[u] ≤ low[v] を満たす

  

出題例

例題: ABC334 G - Christmas Color Grid 2？