graph/find_vertex_cover.hpp

• View this file on GitHub
• Last update: 2024-03-29 11:46:13+09:00
• Include: #include "graph/find_vertex_cover.hpp"
• Link: https://codeforces.com/contest/164/problem/D

Code

// 大きさ K 以下の頂点被覆があればそれを返す
// NK*1.618^K くらい
// path-cycle を何とかするともっと早くなる
// グラフの持ち方がいまいちかも
// https://codeforces.com/contest/164/problem/D
template <typename GT>
vc<int> find_vertex_cover(GT G, int K) {
  int N = G.N;
  vv(bool, adj, N, N);
  for (auto& e: G.edges) {
    assert(e.frm != e.to);
    adj[e.frm][e.to] = adj[e.to][e.frm] = 1;
  }
  vc<int> deg(N);
  FOR(v, N) deg[v] = SUM<int>(adj[v]);

  if (K == 0) return {};

  vc<bool> used(N);
  vc<int> S;
  bool end = 0;
  int M = SUM<int>(deg) / 2;

  auto on = [&](int v) -> void {
    assert(!used[v]);
    M -= deg[v];
    FOR(w, N) {
      if (!used[w] && adj[v][w]) { deg[v]--, deg[w]--; }
    }
    assert(deg[v] == 0);
    used[v] = 1;
    S.eb(v);
  };
  auto off = [&](int v) -> void {
    assert(S.back() == v);
    S.pop_back();
    used[v] = 0;
    FOR(w, N) {
      if (!used[w] && adj[v][w]) { deg[v]++, deg[w]++; }
    }
    M += deg[v];
  };

  auto dfs = [&](auto& dfs) -> void {
    if (end) return;
    int c = max_element(all(deg)) - deg.begin();
    if (deg[c] * (K - len(S)) < M) { return; }
    if (deg[c] == 0) {
      assert(M == 0);
      end = 1;
      return;
    }
    if (len(S) == K) { return; }
    on(c);
    dfs(dfs);
    if (end) return;
    off(c);
    if (deg[c] == 1) return;
    if (len(S) + deg[c] > K) return;
    int k = len(S);
    FOR(v, N) {
      if (adj[v][c] && !used[v]) { on(v); }
    }
    dfs(dfs);
    if (end) return;
    while (len(S) > k) { off(S.back()); }
  };
  dfs(dfs);
  if (!end) assert(S.empty());
  return S;
}

#line 1 "graph/find_vertex_cover.hpp"

// 大きさ K 以下の頂点被覆があればそれを返す
// NK*1.618^K くらい
// path-cycle を何とかするともっと早くなる
// グラフの持ち方がいまいちかも
// https://codeforces.com/contest/164/problem/D
template <typename GT>
vc<int> find_vertex_cover(GT G, int K) {
  int N = G.N;
  vv(bool, adj, N, N);
  for (auto& e: G.edges) {
    assert(e.frm != e.to);
    adj[e.frm][e.to] = adj[e.to][e.frm] = 1;
  }
  vc<int> deg(N);
  FOR(v, N) deg[v] = SUM<int>(adj[v]);

  if (K == 0) return {};

  vc<bool> used(N);
  vc<int> S;
  bool end = 0;
  int M = SUM<int>(deg) / 2;

  auto on = [&](int v) -> void {
    assert(!used[v]);
    M -= deg[v];
    FOR(w, N) {
      if (!used[w] && adj[v][w]) { deg[v]--, deg[w]--; }
    }
    assert(deg[v] == 0);
    used[v] = 1;
    S.eb(v);
  };
  auto off = [&](int v) -> void {
    assert(S.back() == v);
    S.pop_back();
    used[v] = 0;
    FOR(w, N) {
      if (!used[w] && adj[v][w]) { deg[v]++, deg[w]++; }
    }
    M += deg[v];
  };

  auto dfs = [&](auto& dfs) -> void {
    if (end) return;
    int c = max_element(all(deg)) - deg.begin();
    if (deg[c] * (K - len(S)) < M) { return; }
    if (deg[c] == 0) {
      assert(M == 0);
      end = 1;
      return;
    }
    if (len(S) == K) { return; }
    on(c);
    dfs(dfs);
    if (end) return;
    off(c);
    if (deg[c] == 1) return;
    if (len(S) + deg[c] > K) return;
    int k = len(S);
    FOR(v, N) {
      if (adj[v][c] && !used[v]) { on(v); }
    }
    dfs(dfs);
    if (end) return;
    while (len(S) > k) { off(S.back()); }
  };
  dfs(dfs);
  if (!end) assert(S.empty());
  return S;
}

Back to top page