グラフ/補グラフの連結成分分解
(test/graph/connencted_component_of_complement_graph.test.cpp)

• View this file on GitHub
• Last update: 2024-05-23 20:00:52+09:00
• Problem: https://judge.yosupo.jp/problem/connected_components_of_complement_graph

Depends on

• union-find (include/emthrm/data_structure/union-find/union-find.hpp)
• 補グラフの連結成分分解 (include/emthrm/graph/connencted_component_of_complement_graph.hpp)
• 辺 (include/emthrm/graph/edge.hpp)

Code

/*
 * @title グラフ/補グラフの連結成分分解
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/connected_components_of_complement_graph
 */

#include <iostream>
#include <ranges>
#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;
    graph[a].emplace_back(a, b);
    graph[b].emplace_back(b, a);
  }
  emthrm::UnionFind union_find =
      emthrm::connencted_component_of_complement_graph(graph);
  int k = 0;
  std::vector<std::vector<int>> v(n);
  for (const int i : std::views::iota(0, n)) {
    v[union_find.root(i)].emplace_back(i);
    if (union_find.root(i) == i) ++k;
  }
  std::cout << k << '\n';
  for (const std::vector<int>& v_i : v) {
    if (v_i.empty()) continue;
    std::cout << v_i.size();
    for (const int v_ij : v_i) std::cout << ' ' << v_ij;
    std::cout << '\n';
  }
  return 0;
}

#line 1 "test/graph/connencted_component_of_complement_graph.test.cpp"
/*
 * @title グラフ/補グラフの連結成分分解
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/connected_components_of_complement_graph
 */

#include <iostream>
#include <ranges>
#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"



#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;
    graph[a].emplace_back(a, b);
    graph[b].emplace_back(b, a);
  }
  emthrm::UnionFind union_find =
      emthrm::connencted_component_of_complement_graph(graph);
  int k = 0;
  std::vector<std::vector<int>> v(n);
  for (const int i : std::views::iota(0, n)) {
    v[union_find.root(i)].emplace_back(i);
    if (union_find.root(i) == i) ++k;
  }
  std::cout << k << '\n';
  for (const std::vector<int>& v_i : v) {
    if (v_i.empty()) continue;
    std::cout << v_i.size();
    for (const int v_ij : v_i) std::cout << ' ' << v_ij;
    std::cout << '\n';
  }
  return 0;
}

Back to top page