BFS on a Complement Graph
(graph/complement_bfs.hpp)

• View this file on GitHub
• Last update: 2023-09-10 15:17:33+09:00
• Include: #include "graph/complement_bfs.hpp"

Description

補グラフで幅優先探索を行う．

Operations

• vector<int> complement_bfs(vector<vector<int>> Gcomp, int s)
  • グラフ $G$ の補グラフが与えられたとき， $G$ 上で $s$ から各頂点への最短距離を求める
  • 時間計算量: $O(n+m)$

Reference

• ABC319 G - Counting Shortest Paths 解説
• verify: https://atcoder.jp/contests/abc319/submissions/45437018

Code

#pragma once
#include <numeric>
#include <queue>
#include <vector>

std::vector<int> complement_bfs(const std::vector<std::vector<int>>& Gcomp,
                                int s) {
    std::vector<int> dist(Gcomp.size(), -1);
    dist[s] = 0;

    std::vector<int> unvisited(Gcomp.size() - 1);
    std::iota(unvisited.begin(), unvisited.end(), 1);

    std::vector<bool> not_neighbor(Gcomp.size());

    std::queue<int> que;
    que.push(s);

    while (!que.empty()) {
        int v = que.front();
        que.pop();

        for (int u : Gcomp[v]) {
            not_neighbor[u] = true;
        }

        std::vector<int> nxt_unvisited;

        for (int u : unvisited) {
            if (not_neighbor[u]) {
                nxt_unvisited.push_back(u);
            } else {
                dist[u] = dist[v] + 1;
                que.push(u);
            }
        }

        unvisited.swap(nxt_unvisited);

        for (int u : Gcomp[v]) {
            not_neighbor[u] = false;
        }
    }

    return dist;
}

#line 2 "graph/complement_bfs.hpp"
#include <numeric>
#include <queue>
#include <vector>

std::vector<int> complement_bfs(const std::vector<std::vector<int>>& Gcomp,
                                int s) {
    std::vector<int> dist(Gcomp.size(), -1);
    dist[s] = 0;

    std::vector<int> unvisited(Gcomp.size() - 1);
    std::iota(unvisited.begin(), unvisited.end(), 1);

    std::vector<bool> not_neighbor(Gcomp.size());

    std::queue<int> que;
    que.push(s);

    while (!que.empty()) {
        int v = que.front();
        que.pop();

        for (int u : Gcomp[v]) {
            not_neighbor[u] = true;
        }

        std::vector<int> nxt_unvisited;

        for (int u : unvisited) {
            if (not_neighbor[u]) {
                nxt_unvisited.push_back(u);
            } else {
                dist[u] = dist[v] + 1;
                que.push(u);
            }
        }

        unvisited.swap(nxt_unvisited);

        for (int u : Gcomp[v]) {
            not_neighbor[u] = false;
        }
    }

    return dist;
}

Back to top page