graph/bitset/scc_bitset.hpp

• View this file on GitHub
• Last update: 2024-04-27 11:55:26+09:00
• Include: #include "graph/bitset/scc_bitset.hpp"
• Link: https://codeforces.com/contest/641/problem/F

Depends on

• graph/blackbox/scc.hpp

Code

#include "graph/blackbox/scc.hpp"

// 密グラフのscc
// O(N^2/w)
// https://codeforces.com/contest/641/problem/F
pair<int, vc<int>> scc_bitset(vc<My_Bitset> G) {
  using BS = My_Bitset;
  const int N = len(G);
  vc<BS> RG(N, BS(N));
  FOR(i, N) FOR(j, N) RG[i][j] = 1 * G[j][i];

  BS b0(N, 1);
  BS b1(N, 1);

  auto set_used = [&](int v, bool rev) -> void {
    if (!rev) b0[v] = 0;
    if (rev) b1[v] = 0;
  };

  auto find_unused = [&](int v, bool rev) -> int {
    if (!rev) {
      BS &x = G[v];
      x &= b0.range(0, len(x));
      int p = x.prev(len(x));
      x.resize(p + 1);
      return p;
    }
    BS &x = RG[v];
    x &= b1.range(0, len(x));
    int p = x.prev(len(x));
    x.resize(p + 1);
    return p;
  };
  return blackbox_scc(N, set_used, find_unused);
}

#line 1 "graph/blackbox/scc.hpp"

// G とその reverse graph に対して dfs を行う
// topo順は正しいが, 探索で見た辺を集めても scc_dag は得られないので注意
// set_used(int v, bool rev)
// find_used(int v, bool rev)
// find は set よりあとに呼ばれる
template <typename F1, typename F2>
pair<int, vc<int>> blackbox_scc(int N, F1 set_used, F2 find_unused) {
  vc<int> ord(N);
  {
    int nxt = N;
    vc<bool> vis(N);
    auto dfs = [&](auto& dfs, int v) -> void {
      assert(v < N && !vis[v]);
      vis[v] = 1, set_used(v, false);
      while (1) {
        int to = find_unused(v, false);
        assert(to < N);
        if (to == -1) break;
        dfs(dfs, to);
      }
      ord[--nxt] = v;
    };
    FOR(v, N) if (!vis[v]) dfs(dfs, v);
  }
  vc<int> comp(N);
  int nc = 0;
  vc<bool> vis(N);
  auto dfs = [&](auto& dfs, int v) -> void {
    vis[v] = 1, comp[v] = nc, set_used(v, true);
    while (1) {
      int to = find_unused(v, true);
      assert(to < N);
      if (to == -1) break;
      dfs(dfs, to);
    }
  };
  for (auto&& v: ord) {
    if (!vis[v]) dfs(dfs, v), ++nc;
  }
  return {nc, comp};
}
#line 2 "graph/bitset/scc_bitset.hpp"

// 密グラフのscc
// O(N^2/w)
// https://codeforces.com/contest/641/problem/F
pair<int, vc<int>> scc_bitset(vc<My_Bitset> G) {
  using BS = My_Bitset;
  const int N = len(G);
  vc<BS> RG(N, BS(N));
  FOR(i, N) FOR(j, N) RG[i][j] = 1 * G[j][i];

  BS b0(N, 1);
  BS b1(N, 1);

  auto set_used = [&](int v, bool rev) -> void {
    if (!rev) b0[v] = 0;
    if (rev) b1[v] = 0;
  };

  auto find_unused = [&](int v, bool rev) -> int {
    if (!rev) {
      BS &x = G[v];
      x &= b0.range(0, len(x));
      int p = x.prev(len(x));
      x.resize(p + 1);
      return p;
    }
    BS &x = RG[v];
    x &= b1.range(0, len(x));
    int p = x.prev(len(x));
    x.resize(p + 1);
    return p;
  };
  return blackbox_scc(N, set_used, find_unused);
}

Back to top page