graph/blackbox/interval_graph_unionfind.hpp

• View this file on GitHub
• Last update: 2024-03-10 03:27:25+09:00
• Include: #include "graph/blackbox/interval_graph_unionfind.hpp"
• Link: https://codeforces.com/contest/1209/problem/G1

Depends on

• ds/unionfind/unionfind.hpp

Code

#include "ds/unionfind/unionfind.hpp"

// 区間は [L, R). 交わりが空でないものを union．
// https://codeforces.com/contest/1209/problem/G1
UnionFind interval_graph_unionfind(int N, vc<int> L, vc<int> R) {
  // 包含のある場合含まれているものをマージして削除する
  // 包含がなくなったら隣接しているものをマージする
  assert(len(L) == N && len(R) == N);
  vc<int> I(N);
  FOR(i, N) I[i] = i;

  sort(all(I), [&](auto& a, auto& b) -> bool {
    if (L[a] != L[b]) return L[a] < L[b];
    return R[a] > R[b];
  });

  UnionFind uf(N);
  vc<int> keep;
  for (auto& j: I) {
    if (!keep.empty()) {
      int i = keep.back();
      if (R[j] <= R[i] && R[j] - L[j] < R[i] - L[i]) {
        uf.merge(i, j);
        continue;
      }
    }
    keep.eb(j);
  }
  FOR(k, len(keep) - 1) {
    int i = keep[k], j = keep[k + 1];
    if (max(L[i], L[j]) < min(R[i], R[j])) uf.merge(i, j);
  }
  return uf;
}

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

#line 2 "ds/unionfind/unionfind.hpp"

struct UnionFind {
  int n, n_comp;
  vc<int> dat; // par or (-size)
  UnionFind(int n = 0) { build(n); }

  void build(int m) {
    n = m, n_comp = m;
    dat.assign(n, -1);
  }

  void reset() { build(n); }

  int operator[](int x) {
    while (dat[x] >= 0) {
      int pp = dat[dat[x]];
      if (pp < 0) { return dat[x]; }
      x = dat[x] = pp;
    }
    return x;
  }

  ll size(int x) {
    x = (*this)[x];
    return -dat[x];
  }

  bool merge(int x, int y) {
    x = (*this)[x], y = (*this)[y];
    if (x == y) return false;
    if (-dat[x] < -dat[y]) swap(x, y);
    dat[x] += dat[y], dat[y] = x, n_comp--;
    return true;
  }

  vc<int> get_all() {
    vc<int> A(n);
    FOR(i, n) A[i] = (*this)[i];
    return A;
  }
};
#line 3 "graph/blackbox/interval_graph_unionfind.hpp"

// 区間は [L, R). 交わりが空でないものを union．
// https://codeforces.com/contest/1209/problem/G1
UnionFind interval_graph_unionfind(int N, vc<int> L, vc<int> R) {
  // 包含のある場合含まれているものをマージして削除する
  // 包含がなくなったら隣接しているものをマージする
  assert(len(L) == N && len(R) == N);
  vc<int> I(N);
  FOR(i, N) I[i] = i;

  sort(all(I), [&](auto& a, auto& b) -> bool {
    if (L[a] != L[b]) return L[a] < L[b];
    return R[a] > R[b];
  });

  UnionFind uf(N);
  vc<int> keep;
  for (auto& j: I) {
    if (!keep.empty()) {
      int i = keep.back();
      if (R[j] <= R[i] && R[j] - L[j] < R[i] - L[i]) {
        uf.merge(i, j);
        continue;
      }
    }
    keep.eb(j);
  }
  FOR(k, len(keep) - 1) {
    int i = keep[k], j = keep[k + 1];
    if (max(L[i], L[j]) < min(R[i], R[j])) uf.merge(i, j);
  }
  return uf;
}

Back to top page