complement_graph_components.hpp¶

SECTIONGraph INCLUDEnoya/complement_graph_components.hpp

在线性对数级复杂度内求补图的连通分量，而不显式建立所有补边。

Complexity: Time: O(V + E). Space: O(V + E).

AC 记录：connected_components_of_complement_graph。

Implementation¶

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(V + E).
/// Space: O(V + E).

#include <cassert>
#include <list>
#include <queue>
#include <utility>
#include <vector>

namespace noya {

/// @brief Connected components of the complement of an undirected graph.
inline std::vector<std::vector<int>>
complement_graph_components(int n, const std::vector<std::pair<int, int>> &es) {
  assert(n >= 0);
  std::vector<std::vector<int>> g(n);
  for (auto [a, b] : es) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    g[a].push_back(b);
    g[b].push_back(a);
  }

  std::list<int> unv;
  for (int u = 0; u < n; u++) {
    unv.push_back(u);
  }
  std::vector<int> vis(n);
  int tim = 0;
  std::vector<std::vector<int>> dsu;
  while (!unv.empty()) {
    int s = unv.front();
    unv.pop_front();
    dsu.push_back({s});
    std::queue<int> q;
    q.push(s);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      ++tim;
      for (int nxt : g[u]) {
        vis[nxt] = tim;
      }
      for (auto it = unv.begin(); it != unv.end();) {
        int can = *it;
        if (vis[can] == tim) {
          ++it;
        } else {
          dsu.back().push_back(can);
          q.push(can);
          it = unv.erase(it);
        }
      }
    }
  }
  return dsu;
}

} // namespace noya

#ifndef NOYA_COMPLEMENT_GRAPH_COMPONENTS_HPP
#define NOYA_COMPLEMENT_GRAPH_COMPONENTS_HPP 1

/// @complexity Time: O(V + E).
/// Space: O(V + E).

#include <cassert>
#include <list>
#include <queue>
#include <utility>
#include <vector>

namespace noya {

/// @brief Connected components of the complement of an undirected graph.
inline std::vector<std::vector<int>>
complement_graph_components(int n, const std::vector<std::pair<int, int>> &es) {
  assert(n >= 0);
  std::vector<std::vector<int>> g(n);
  for (auto [a, b] : es) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    g[a].push_back(b);
    g[b].push_back(a);
  }

  std::list<int> unv;
  for (int u = 0; u < n; u++) {
    unv.push_back(u);
  }
  std::vector<int> vis(n);
  int tim = 0;
  std::vector<std::vector<int>> dsu;
  while (!unv.empty()) {
    int s = unv.front();
    unv.pop_front();
    dsu.push_back({s});
    std::queue<int> q;
    q.push(s);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      ++tim;
      for (int nxt : g[u]) {
        vis[nxt] = tim;
      }
      for (auto it = unv.begin(); it != unv.end();) {
        int can = *it;
        if (vis[can] == tim) {
          ++it;
        } else {
          dsu.back().push_back(can);
          q.push(can);
          it = unv.erase(it);
        }
      }
    }
  }
  return dsu;
}

} // namespace noya

#endif // NOYA_COMPLEMENT_GRAPH_COMPONENTS_HPP

#include <cassert>
#include <list>
#include <queue>
#include <utility>
#include <vector>

/// @complexity Time: O(V + E).
/// Space: O(V + E).

namespace noya {

/// @brief Connected components of the complement of an undirected graph.
inline std::vector<std::vector<int>>
complement_graph_components(int n, const std::vector<std::pair<int, int>> &es) {
  assert(n >= 0);
  std::vector<std::vector<int>> g(n);
  for (auto [a, b] : es) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    g[a].push_back(b);
    g[b].push_back(a);
  }

  std::list<int> unv;
  for (int u = 0; u < n; u++) {
    unv.push_back(u);
  }
  std::vector<int> vis(n);
  int tim = 0;
  std::vector<std::vector<int>> dsu;
  while (!unv.empty()) {
    int s = unv.front();
    unv.pop_front();
    dsu.push_back({s});
    std::queue<int> q;
    q.push(s);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      ++tim;
      for (int nxt : g[u]) {
        vis[nxt] = tim;
      }
      for (auto it = unv.begin(); it != unv.end();) {
        int can = *it;
        if (vis[can] == tim) {
          ++it;
        } else {
          dsu.back().push_back(can);
          q.push(can);
          it = unv.erase(it);
        }
      }
    }
  }
  return dsu;
}

} // namespace noya