This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub gyouzasushi/library
#define PROBLEM \ "https://judge.yosupo.jp/problem/connected_components_of_complement_graph" #include <iostream> #include "graph/bfs_tree_of_complement.hpp" int main() { int n, m; std::cin >> n >> m; std::vector<std::vector<int>> g(n); for (int i = 0; i < m; i++) { int u, v; std::cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } std::vector adj = bfs_tree_of_complement(g); std::vector<std::vector<int>> ans; std::vector used(n, false); auto dfs = [&](auto dfs, int u) -> void { used[u] = true; ans.back().push_back(u); for (int v : adj[u]) { dfs(dfs, v); } }; for (int i = 0; i < n; i++) { if (used[i]) continue; ans.push_back({}); dfs(dfs, i); } int k = ans.size(); std::cout << k << '\n'; for (const std::vector<int>& v : ans) { int l = v.size(); std::cout << l << ' '; for (int i = 0; i < l; i++) { std::cout << v[i] << " \n"[i == l - 1]; } } }
#line 1 "test/library-checker/connected_components_of_complement_graph.test.cpp" #define PROBLEM \ "https://judge.yosupo.jp/problem/connected_components_of_complement_graph" #include <iostream> #line 2 "graph/bfs_tree_of_complement.hpp" #include <algorithm> #include <numeric> #include <queue> #include <vector> std::vector<std::vector<int>> bfs_tree_of_complement( const std::vector<std::vector<int>>& g) { int n = int(g.size()); std::vector<std::vector<int>> ret(n); std::vector<bool> seen(n); std::vector<bool> banned(n); std::queue<int> q; std::vector<int> s(n), t; std::iota(s.begin(), s.end(), 0); for (int i = 0; i < n; i++) { if (seen[i]) continue; seen[i] = true; q.push(i); while (!q.empty()) { int u = q.front(); q.pop(); seen[u] = true; for (int v : g[u]) { banned[v] = true; } for (int v : s) { if (banned[v]) { t.push_back(v); } else if (!seen[v]) { ret[u].push_back(v); q.push(v); } } s = std::move(t); for (int v : g[u]) { banned[v] = false; } } } return ret; } #line 6 "test/library-checker/connected_components_of_complement_graph.test.cpp" int main() { int n, m; std::cin >> n >> m; std::vector<std::vector<int>> g(n); for (int i = 0; i < m; i++) { int u, v; std::cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } std::vector adj = bfs_tree_of_complement(g); std::vector<std::vector<int>> ans; std::vector used(n, false); auto dfs = [&](auto dfs, int u) -> void { used[u] = true; ans.back().push_back(u); for (int v : adj[u]) { dfs(dfs, v); } }; for (int i = 0; i < n; i++) { if (used[i]) continue; ans.push_back({}); dfs(dfs, i); } int k = ans.size(); std::cout << k << '\n'; for (const std::vector<int>& v : ans) { int l = v.size(); std::cout << l << ' '; for (int i = 0; i < l; i++) { std::cout << v[i] << " \n"[i == l - 1]; } } }