C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title グラフ/補グラフの連結成分分解 * * verification-helper: IGNORE * verification-helper: PROBLEM https://codeforces.com/problemset/problem/1242/B */ #include <iostream> #include <vector> #include "emthrm/data_structure/union-find/union-find.hpp" #include "emthrm/graph/edge.hpp" #include "emthrm/graph/connencted_component_of_complement_graph.hpp" int main() { int n, m; std::cin >> n >> m; std::vector<std::vector<emthrm::Edge<bool>>> graph(n); while (m--) { int a, b; std::cin >> a >> b; --a; --b; graph[a].emplace_back(a, b); graph[b].emplace_back(b, a); } emthrm::UnionFind union_find = emthrm::connencted_component_of_complement_graph(graph); int ans = 0; for (int i = 0; i < n; ++i) { ans += union_find.root(i) == i; } std::cout << ans - 1 << '\n'; return 0; }
#line 1 "test/graph/connencted_component_of_complement_graph.test.cpp" /* * @title グラフ/補グラフの連結成分分解 * * verification-helper: IGNORE * verification-helper: PROBLEM https://codeforces.com/problemset/problem/1242/B */ #include <iostream> #include <vector> #line 1 "include/emthrm/data_structure/union-find/union-find.hpp" #include <utility> #line 6 "include/emthrm/data_structure/union-find/union-find.hpp" namespace emthrm { struct UnionFind { explicit UnionFind(const int n) : data(n, -1) {} int root(const int ver) { return data[ver] < 0 ? ver : data[ver] = root(data[ver]); } bool unite(int u, int v) { u = root(u); v = root(v); if (u == v) return false; if (data[u] > data[v]) std::swap(u, v); data[u] += data[v]; data[v] = u; return true; } bool is_same(const int u, const int v) { return root(u) == root(v); } int size(const int ver) { return -data[root(ver)]; } private: std::vector<int> data; }; } // namespace emthrm #line 1 "include/emthrm/graph/edge.hpp" /** * @title 辺 */ #ifndef EMTHRM_GRAPH_EDGE_HPP_ #define EMTHRM_GRAPH_EDGE_HPP_ #include <compare> namespace emthrm { template <typename CostType> struct Edge { CostType cost; int src, dst; explicit Edge(const int src, const int dst, const CostType cost = 0) : cost(cost), src(src), dst(dst) {} auto operator<=>(const Edge& x) const = default; }; } // namespace emthrm #endif // EMTHRM_GRAPH_EDGE_HPP_ #line 1 "include/emthrm/graph/connencted_component_of_complement_graph.hpp" #include <ranges> #line 6 "include/emthrm/graph/connencted_component_of_complement_graph.hpp" #line 1 "include/emthrm/graph/edge.hpp" /** * @title 辺 */ #ifndef EMTHRM_GRAPH_EDGE_HPP_ #define EMTHRM_GRAPH_EDGE_HPP_ #include <compare> namespace emthrm { template <typename CostType> struct Edge { CostType cost; int src, dst; explicit Edge(const int src, const int dst, const CostType cost = 0) : cost(cost), src(src), dst(dst) {} auto operator<=>(const Edge& x) const = default; }; } // namespace emthrm #endif // EMTHRM_GRAPH_EDGE_HPP_ #line 9 "include/emthrm/graph/connencted_component_of_complement_graph.hpp" namespace emthrm { template <typename CostType> UnionFind connencted_component_of_complement_graph( const std::vector<std::vector<Edge<CostType>>>& graph) { const int n = graph.size(); UnionFind union_find(n); const auto check = [&graph, n, &union_find](const int ver) -> void { std::vector<bool> is_adjacent(n, false); for (const int e : graph[ver] | std::views::transform(&Edge<CostType>::dst)) { is_adjacent[e] = true; } for (int i = 0; i < n; ++i) { if (!is_adjacent[i]) union_find.unite(ver, i); } }; int argmin_deg = 0; for (int i = 1; i < n; ++i) { if (graph[i].size() < graph[argmin_deg].size()) argmin_deg = i; } check(argmin_deg); for (const int e : graph[argmin_deg] | std::views::transform(&Edge<CostType>::dst)) { check(e); } return union_find; } } // namespace emthrm #line 14 "test/graph/connencted_component_of_complement_graph.test.cpp" int main() { int n, m; std::cin >> n >> m; std::vector<std::vector<emthrm::Edge<bool>>> graph(n); while (m--) { int a, b; std::cin >> a >> b; --a; --b; graph[a].emplace_back(a, b); graph[b].emplace_back(b, a); } emthrm::UnionFind union_find = emthrm::connencted_component_of_complement_graph(graph); int ans = 0; for (int i = 0; i < n; ++i) { ans += union_find.root(i) == i; } std::cout << ans - 1 << '\n'; return 0; }