library/graphs/dsu.hpp

• View this file on GitHub
• Last update: 2023-01-08 14:16:34-05:00
• Include: #include "library/graphs/dsu.hpp"

Required by

• library/graphs/kruskal.hpp

Verified with

• verify/aizu/aizu-GRL_2_A.test.cpp
• verify/codeforces/codeforces-1463E.test.cpp
• verify/codeforces/codeforces-1494F.test.cpp
• verify/codeforces/codeforces-1553G.test.cpp
• verify/yosupo/yosupo-unionfind.test.cpp

Code

#pragma once

struct DSU {
  std::vector<int> e;

  DSU() = default;
  DSU(int n) { init(n); }

  void init(int n) { e = std::vector<int>(n, -1); }

  int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }

  bool same_set(int a, int b) { return get(a) == get(b); }

  int size(int x) { return -e[get(x)]; }

  bool unite(int x, int y) {
    x = get(x), y = get(y);
    if (x == y) return false;
    if (e[x] > e[y]) std::swap(x, y);
    e[x] += e[y];
    e[y] = x;
    return true;
  }
};

struct DSU {
  std::vector<int> e;

  DSU() = default;
  DSU(int n) { init(n); }

  void init(int n) { e = std::vector<int>(n, -1); }

  int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }

  bool same_set(int a, int b) { return get(a) == get(b); }

  int size(int x) { return -e[get(x)]; }

  bool unite(int x, int y) {
    x = get(x), y = get(y);
    if (x == y) return false;
    if (e[x] > e[y]) std::swap(x, y);
    e[x] += e[y];
    e[y] = x;
    return true;
  }
};

Back to top page