sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#include "graph/complement_bfs.hpp"
補グラフで幅優先探索を行う.
vector<int> complement_bfs(vector<vector<int>> Gcomp, int s)
#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; }