Lowlink
(graph/lowlink.hpp)

• View this file on GitHub
• Last update: 2024-01-08 13:32:33+09:00
• Include: #include "graph/lowlink.hpp"

Description

Lowlink はグラフの橋や関節点などを求める際に有効な概念である．グラフの DFS tree において，頂点 $v$ の訪問時刻を ord[v] としたとき，$v$ から後退辺 (DFS tree に含まれない辺) を高々1回用いて到達することができる頂点の ord の最小値 low[v] を lowlink という．

辺 $(u, v)$ が橋であることの必要十分条件は ord[u] < low[v] が成り立つことである．

頂点 $v$ が関節点であることの必要十分条件は

• $v$ が DFS tree の根であり，かつ2つ以上の子を持つ
• $v$ が DFS tree の根ではなく，かつ $v$ のある子 $c$ について ord[v] <= low[c] が成り立つ

のどちらかが成り立つことである．

空間計算量: $O(V + E)$

Operations

• Lowlink(vector<vector<int>> G)
  • グラフ $G$ の隣接リストが与えられたとき，$G$ の橋と関節点を求める
  • 時間計算量: $O(V + E)$
• bool is_bridge(int u, int v)
  • 辺 $uv$ が橋かどうか判定する
  • 時間計算量: $O(1)$

Reference

• 橋と関節点, lowlink

Required by

• Biconnected Components (graph/biconnected_components.hpp)
• 2-Edge-Connected Components (graph/two_edge_connected_components.hpp)

Verified with

• test/aoj/GRL_3_A.test.cpp
• test/aoj/GRL_3_B.test.cpp
• test/yosupo/biconnected_components.test.cpp
• test/yosupo/two_edge_connected_components.test.cpp

Code

#pragma once
#include <algorithm>
#include <utility>
#include <vector>

class Lowlink {
   public:
    std::vector<int> ord, low;
    std::vector<std::pair<int, int>> bridge;
    std::vector<int> articulation;

    Lowlink() = default;
    explicit Lowlink(const std::vector<std::vector<int>>& G)
        : ord(G.size(), -1), low(G.size()), G(G) {
        for (int i = 0; i < (int)G.size(); ++i) {
            if (ord[i] == -1) dfs(i, -1);
        }
    }

    bool is_bridge(int u, int v) const {
        if (ord[u] > ord[v]) std::swap(u, v);
        return ord[u] < low[v];
    }

   private:
    std::vector<std::vector<int>> G;
    int k = 0;

    void dfs(int v, int p) {
        ord[v] = k++;
        low[v] = ord[v];
        bool is_articulation = false, checked = false;
        int cnt = 0;
        for (int c : G[v]) {
            if (c == p && !checked) {
                checked = true;
                continue;
            }
            if (ord[c] == -1) {
                ++cnt;
                dfs(c, v);
                low[v] = std::min(low[v], low[c]);
                if (p != -1 && ord[v] <= low[c]) is_articulation = true;
                if (ord[v] < low[c]) bridge.push_back(std::minmax(v, c));
            } else {
                low[v] = std::min(low[v], ord[c]);
            }
        }
        if (p == -1 && cnt > 1) is_articulation = true;
        if (is_articulation) articulation.push_back(v);
    }
};

#line 2 "graph/lowlink.hpp"
#include <algorithm>
#include <utility>
#include <vector>

class Lowlink {
   public:
    std::vector<int> ord, low;
    std::vector<std::pair<int, int>> bridge;
    std::vector<int> articulation;

    Lowlink() = default;
    explicit Lowlink(const std::vector<std::vector<int>>& G)
        : ord(G.size(), -1), low(G.size()), G(G) {
        for (int i = 0; i < (int)G.size(); ++i) {
            if (ord[i] == -1) dfs(i, -1);
        }
    }

    bool is_bridge(int u, int v) const {
        if (ord[u] > ord[v]) std::swap(u, v);
        return ord[u] < low[v];
    }

   private:
    std::vector<std::vector<int>> G;
    int k = 0;

    void dfs(int v, int p) {
        ord[v] = k++;
        low[v] = ord[v];
        bool is_articulation = false, checked = false;
        int cnt = 0;
        for (int c : G[v]) {
            if (c == p && !checked) {
                checked = true;
                continue;
            }
            if (ord[c] == -1) {
                ++cnt;
                dfs(c, v);
                low[v] = std::min(low[v], low[c]);
                if (p != -1 && ord[v] <= low[c]) is_articulation = true;
                if (ord[v] < low[c]) bridge.push_back(std::minmax(v, c));
            } else {
                low[v] = std::min(low[v], ord[c]);
            }
        }
        if (p == -1 && cnt > 1) is_articulation = true;
        if (is_articulation) articulation.push_back(v);
    }
};

Back to top page