data-structure/union-find-enumerate.hpp

• View this file on GitHub
• Last update: 2024-04-28 09:13:11+09:00
• Include: #include "data-structure/union-find-enumerate.hpp"

Required by

• data-structure/parallel-union-find.hpp

Verified with

• verify/verify-unit-test/parallel-union-find.test.cpp

Code

#pragma once

#include <vector>
using namespace std;

struct UnionFindEnumerate {
  vector<int> data, nxt;
  UnionFindEnumerate(int N) : data(N, -1), nxt(N) {
    for (int i = 0; i < N; i++) nxt[i] = i;
  }

  int find(int k) { return data[k] < 0 ? k : data[k] = find(data[k]); }

  int unite(int x, int y) {
    if ((x = find(x)) == (y = find(y))) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    swap(nxt[x], nxt[y]);
    return true;
  }

  // f(x, y) : x に y をマージ
  template <typename F>
  int unite(int x, int y, const F &f) {
    if ((x = find(x)) == (y = find(y))) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    f(x, y);
    swap(nxt[x], nxt[y]);
    return true;
  }

  int size(int k) { return -data[find(k)]; }

  int same(int x, int y) { return find(x) == find(y); }

  vector<int> enumerate(int i) {
    vector<int> res{i};
    for (int j = nxt[i]; j != i; j = nxt[j]) res.push_back(j);
    return res;
  }
};

#line 2 "data-structure/union-find-enumerate.hpp"

#include <vector>
using namespace std;

struct UnionFindEnumerate {
  vector<int> data, nxt;
  UnionFindEnumerate(int N) : data(N, -1), nxt(N) {
    for (int i = 0; i < N; i++) nxt[i] = i;
  }

  int find(int k) { return data[k] < 0 ? k : data[k] = find(data[k]); }

  int unite(int x, int y) {
    if ((x = find(x)) == (y = find(y))) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    swap(nxt[x], nxt[y]);
    return true;
  }

  // f(x, y) : x に y をマージ
  template <typename F>
  int unite(int x, int y, const F &f) {
    if ((x = find(x)) == (y = find(y))) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    f(x, y);
    swap(nxt[x], nxt[y]);
    return true;
  }

  int size(int k) { return -data[find(k)]; }

  int same(int x, int y) { return find(x) == find(y); }

  vector<int> enumerate(int i) {
    vector<int> res{i};
    for (int j = nxt[i]; j != i; j = nxt[j]) res.push_back(j);
    return res;
  }
};

Back to top page