Low Link
(graph/low_link.hpp)

• View this file on GitHub
• Last update: 2023-11-04 02:52:26+09:00
• Include: #include "graph/low_link.hpp"

説明

グラフを渡してlow linkを求める。 $O(N)$

is_bridge(int u, int v)

辺 $u-v$ が橋であるか判定。そのような辺がない場合もfalseを返す。

bridge()

橋を列挙して返す。

articulation()

関節点を列挙して返す。

Depends on

• テンプレート (template/template.hpp)

Verified with

• test/graph/Articulation_Points.test.cpp
• test/graph/Bridges.test.cpp

Code

#pragma once
#include "../template/template.hpp"

namespace lib {

struct low_link {
    low_link(const std::vector<std::vector<int>> &g) : n(g.size()), ord(n, -1), low(n), par(n,-1) {
        int k = 0;
        auto dfs = [&](auto &&self, int v) -> void {
            low[v] = ord[v] = k++;
            int cnt = 0;
            bool is_arti = false, is_second = false;
            for(auto nv: g[v]) {
                if(ord[nv] == -1) {
                    cnt++;
                    par[nv] = v;
                    self(self, nv);
                    chmin(low[v], low[nv]);
                    is_arti |= par[v] != -1 && low[nv] >= ord[v];
                    if(ord[v] < low[nv]) {
                        _bridge.emplace_back(std::minmax(v, nv));
                    }
                }
                else if(nv != par[v] || is_second) {
                    chmin(low[v], ord[nv]);
                }
                else {
                    is_second = true;
                }
            }
            is_arti |= par[v] == -1 && cnt > 1;
            if(is_arti) _articulation.emplace_back(v);
        };
        dfs(dfs, 0);
    }

    bool is_bridge(int u, int v) {
        if(par[v] != u) std::swap(u, v);
        if(par[v] != u) return false;
        return ord[u] < low[v];
    }

    std::vector<std::pair<int,int>> bridge() {
        return _bridge;
    }

    std::vector<int> articulation() {
        return _articulation;
    }
    
    int n;
    std::vector<int> ord, low, par, _articulation;
    std::vector<std::pair<int,int>> _bridge;
};

}

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 3 "graph/low_link.hpp"

namespace lib {

struct low_link {
    low_link(const std::vector<std::vector<int>> &g) : n(g.size()), ord(n, -1), low(n), par(n,-1) {
        int k = 0;
        auto dfs = [&](auto &&self, int v) -> void {
            low[v] = ord[v] = k++;
            int cnt = 0;
            bool is_arti = false, is_second = false;
            for(auto nv: g[v]) {
                if(ord[nv] == -1) {
                    cnt++;
                    par[nv] = v;
                    self(self, nv);
                    chmin(low[v], low[nv]);
                    is_arti |= par[v] != -1 && low[nv] >= ord[v];
                    if(ord[v] < low[nv]) {
                        _bridge.emplace_back(std::minmax(v, nv));
                    }
                }
                else if(nv != par[v] || is_second) {
                    chmin(low[v], ord[nv]);
                }
                else {
                    is_second = true;
                }
            }
            is_arti |= par[v] == -1 && cnt > 1;
            if(is_arti) _articulation.emplace_back(v);
        };
        dfs(dfs, 0);
    }

    bool is_bridge(int u, int v) {
        if(par[v] != u) std::swap(u, v);
        if(par[v] != u) return false;
        return ord[u] < low[v];
    }

    std::vector<std::pair<int,int>> bridge() {
        return _bridge;
    }

    std::vector<int> articulation() {
        return _articulation;
    }
    
    int n;
    std::vector<int> ord, low, par, _articulation;
    std::vector<std::pair<int,int>> _bridge;
};

}

Back to top page