補グラフの BFS

[hitonanode]

https://twitter.com/noshi91/status/1383110660796518401 https://atcoder.jp/contests/abc319/submissions/45420835

struct ComplementGraphBFS {
    int n;
    std::vector<std::vector<int>> g;

    ComplementGraphBFS(int n_, const std::vector<std::pair<int, int>> &edges) : n(n_), g(n) {
        for (auto [u, v] : edges) {
            g.at(u).push_back(v);
            g.at(v).push_back(u);
        }
    }

    void run(int root, auto f) {
        std::vector<int> que{root};
        int ql = 0;

        std::vector<bool> tmp(n, false);
        std::vector<int> unvisited, yet_unvisited;
        for (int i = 0; i < n; ++i) {
            if (root != i) unvisited.push_back(i);
        }

        while (ql < (int)que.size()) {
            yet_unvisited.clear();
            const int now = que.at(ql++);
            for (int nxt : g.at(now)) tmp.at(nxt) = true;
            for (int s : unvisited) {
                if (tmp.at(s)) {
                    yet_unvisited.push_back(s);
                } else {
                    f(now, s); // now -> s is used in complement graph BFS
                    que.push_back(s);
                }
            }
            for (int nxt : g.at(now)) tmp.at(nxt) = false;

            unvisited.swap(yet_unvisited);
        }
    }
};