Shortest Path on Complement Graph
(src/graph/complement_graph_shortest_path.hpp)

• View this file on GitHub
• Last update: 2023-10-01 16:26:05+09:00
• Include: #include "src/graph/complement_graph_shortest_path.hpp"

概要

補グラフ上の頂点 $s$ から各点までの最短経路長を $\mathrm{O}(n + m)$ 時間で求める（ここで、$m$ は元のグラフの辺数）．

補グラフは特に以下のような性質をもつ．

• 各点までの最短路の距離は $\mathrm{O}(\sqrt{m})$ である．
  • ある点までの距離が $d$ とすると、最短経路においてその直前の点を除いた $d - 1$ 点と隣接している必要があることからわかる．
• 各点までの最短路の距離の合計は $\mathrm{O}(n + m)$ である．
  • BFS 木で親の親以上の点に対しては元のグラフで辺が貼られている必要がある．
• もとのグラフが非連結ならばその補グラフは連結．

Links

• https://twitter.com/noshi91/status/1383110660796518401?s=20&t=6NELIs3eDe0fVQxuwfwvow

問題例

• BPC 1 S5 - Temple
• Educational Codeforces Round 142 (Rated for Div. 2) F2. Graph Coloring (hard version)
• AtCoder Beginner Contest 319 G - Counting Shortest Paths

Code

#pragma once
#include <algorithm>
#include <limits>
#include <queue>
#include <vector>

std::vector<int> complement_graph_shortest_path(const std::vector<std::vector<int>>& G, int s) {
    int n = G.size();
    std::vector<int> dist(n, (1 << 30) - 1);
    dist[s] = 0;
    std::vector<int> L;
    std::vector<bool> mark(n, false);
    for (int i = 0; i < n; i++) {
        if (i != s) {
            L.emplace_back(i);
        }
    }
    std::queue<int> Q;
    Q.emplace(s);
    while (not Q.empty()) {
        int v = Q.front();
        Q.pop();
        for (const int& u : G[v]) mark[u] = true;
        std::partition(begin(L), end(L), [&](const int u) { return mark[u]; });
        while (not L.empty()) {
            int u = L.back();
            if (mark[u]) break;
            L.pop_back();
            dist[u] = dist[v] + 1;
            Q.emplace(u);
        }
        for (const int& u : G[v]) mark[u] = false;
    }
    return dist;
}

#line 2 "src/graph/complement_graph_shortest_path.hpp"
#include <algorithm>
#include <limits>
#include <queue>
#include <vector>

std::vector<int> complement_graph_shortest_path(const std::vector<std::vector<int>>& G, int s) {
    int n = G.size();
    std::vector<int> dist(n, (1 << 30) - 1);
    dist[s] = 0;
    std::vector<int> L;
    std::vector<bool> mark(n, false);
    for (int i = 0; i < n; i++) {
        if (i != s) {
            L.emplace_back(i);
        }
    }
    std::queue<int> Q;
    Q.emplace(s);
    while (not Q.empty()) {
        int v = Q.front();
        Q.pop();
        for (const int& u : G[v]) mark[u] = true;
        std::partition(begin(L), end(L), [&](const int u) { return mark[u]; });
        while (not L.empty()) {
            int u = L.back();
            if (mark[u]) break;
            L.pop_back();
            dist[u] = dist[v] + 1;
            Q.emplace(u);
        }
        for (const int& u : G[v]) mark[u] = false;
    }
    return dist;
}

Back to top page