DSU

tác giả: HeRaNO, JuicyMio, Xeonacid, sailordiary, ouuan, Pig-Eat-Earth

Giới thiệu

Tập hợp hợp nhất (Disjoint Set Union - DSU) là một cấu trúc dữ liệu dùng để quản lý các tập hợp của các phần tử, được hiện thực dưới dạng một rừng (forest), trong đó mỗi cây biểu thị một tập hợp, các nút trong cây biểu thị các phần tử tương ứng của tập hợp đó.

Đúng như tên gọi, DSU hỗ trợ hai thao tác:

Hợp nhất (Unite): Hợp nhất tập hợp chứa hai phần tử (hợp nhất các cây tương ứng).
Truy vấn (Find): Truy vấn tập hợp chứa một phần tử (truy vấn nút gốc của cây tương ứng), điều này có thể dùng để phán đoán hai phần tử có thuộc cùng một tập hợp hay không.

DSU sau khi được sửa đổi có thể hỗ trợ việc xóa, di chuyển một phần tử đơn lẻ hoặc duy trì trọng số cạnh trên cây. Sử dụng cây đoạn với điểm mở động, ta còn có thể thực hiện DSU bền vững (Persistent DSU).

Cảnh báo

DSU không thể thực hiện việc tách tập hợp với độ phức tạp thấp.

Khởi tạo

Ban đầu, mỗi phần tử nằm trong một tập hợp riêng biệt, được biểu diễn dưới dạng một cây chỉ có nút gốc. Để tiện cho việc tham khảo, ta đặt cha của nút gốc là chính nó.

Triển khai

C++Python

struct dsu {
  vector<size_t> pa;

  explicit dsu(size_t size) : pa(size) { iota(pa.begin(), pa.end(), 0); }
};

class Dsu:
    def __init__(self, size):
        self.pa = list(range(size))

Truy vấn

Ta cần di chuyển lên trên dọc theo cây cho đến khi tìm thấy nút gốc.

Triển khai

C++Python

size_t dsu::find(size_t x) { return pa[x] == x ? x : find(pa[x]); }

def find(self, x):
    return x if self.pa[x] == x else self.find(self.pa[x])

Nén đường đi (Path Compression)

Mỗi phần tử đi qua trong quá trình truy vấn đều thuộc tập hợp này, ta có thể nối trực tiếp chúng với nút gốc để tăng tốc truy vấn sau này.

Triển khai

C++Python

size_t dsu::find(size_t x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }

def find(self, x):
    if self.pa[x] != x:
        self.pa[x] = self.find(self.pa[x])
    return self.pa[x]

Hợp nhất

Để hợp nhất hai cây, ta chỉ cần nối nút gốc của một cây vào nút gốc của cây kia.

Triển khai

C++Python

void dsu::unite(size_t x, size_t y) { pa[find(x)] = find(y); }

def unite(self, x, y):
    self.pa[self.find(x)] = self.find(y)

Hợp nhất Heuristic (Union by Size/Rank)

Khi hợp nhất, việc chọn nút gốc của cây nào làm nút gốc của cây mới sẽ ảnh hưởng đến độ phức tạp của các thao tác trong tương lai. Ta có thể nối cây có số lượng nút nhỏ hơn hoặc độ sâu nhỏ hơn vào cây kia, để tránh suy biến.

Thảo luận chi tiết về độ phức tạp

Vì ta chỉ cần hỗ trợ các thao tác hợp nhất và truy vấn tập hợp, khi cần hợp nhất hai tập hợp thành một, việc nối cây của tập hợp nào vào cây của tập hợp nào cũng sẽ cho ra kết quả đúng. Nhưng các phương pháp nối khác nhau sẽ có sự khác biệt về độ phức tạp thời gian. Cụ thể, nếu ta nối cây của tập hợp có số lượng nút và độ sâu nhỏ hơn vào một cây tập hợp lớn hơn, rõ ràng so với phương án nối ngược lại, thời gian thực hiện thao tác tìm kiếm sau này sẽ nhỏ hơn (cũng sẽ mang lại độ phức tạp thời gian xấu nhất tối ưu hơn).

Tất nhiên, ta không phải lúc nào cũng gặp các tập hợp mà số lượng nút và độ sâu đều nhỏ hơn. Do đặc điểm về số lượng nút và độ sâu đều dễ duy trì, ta thường chọn một trong hai làm hàm đánh giá. Mà dù chọn cái nào, độ phức tạp thời gian vẫn là \(O (m\alpha(m,n))\), chứng minh cụ thể có thể xem tại các bài báo được trích dẫn trong References.

Trong mã thực tế của các cuộc thi thuật toán, ngay cả khi không sử dụng hợp nhất heuristic, mã nguồn vẫn thường hoàn thành trong thời gian quy định. Trong bài báo của Tarjan¹, đã chứng minh rằng độ phức tạp thời gian xấu nhất của DSU chỉ dùng nén đường đi mà không dùng hợp nhất heuristic là \(O (m \log n)\). Trong bài báo của Andrew Yao², đã chứng minh rằng trong trường hợp trung bình, độ phức tạp thời gian của DSU chỉ dùng nén đường đi mà không dùng hợp nhất heuristic vẫn là \(O (m\alpha(m,n))\).

Nếu chỉ dùng hợp nhất heuristic mà không dùng nén đường đi, độ phức tạp thời gian là \(O(m\log n)\). Vì nén đường đi có thể gây ra sửa đổi lớn trong một lần hợp nhất, đôi khi nén đường đi không phù hợp để sử dụng. Ví dụ, trong DSU bền vững, hoặc DSU + Chia để trị trên cây đoạn, thông thường sử dụng DSU chỉ có hợp nhất heuristic.

Tham khảo cài đặt hợp nhất theo số lượng nút: (Chú ý cần điều chỉnh phương thức khởi tạo)

Triển khai tham khảo

C++Python

struct dsu {
  vector<size_t> pa, size;

  explicit dsu(size_t size_) : pa(size_), size(size_, 1) {
    iota(pa.begin(), pa.end(), 0);
  }

  void unite(size_t x, size_t y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (size[x] < size[y]) swap(x, y);
    pa[y] = x;
    size[x] += size[y];
  }
};

class Dsu:
    def __init__(self, size):
        self.pa = list(range(size))
        self.size = [1] * size

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.pa[y] = x
        self.size[x] += self.size[y]

Triển khai tham khảo

Triển khai hoàn chỉnh của DSU có nén đường đi và hợp nhất theo số lượng nút như sau:

Tham khảo triển khai cho bài toán mẫu Luogu P3367【Mẫu】DSU

C++Python

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

struct DSU {
  std::vector<size_t> pa, size;

  explicit DSU(size_t size_) : pa(size_), size(size_, 1) {
    std::iota(pa.begin(), pa.end(), 0);
  }

  size_t find(size_t x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }

  void unite(size_t x, size_t y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (size[x] < size[y]) std::swap(x, y);
    pa[y] = x;
    size[x] += size[y];
  }
};

int main() {
  int n, m;
  std::cin >> n >> m;
  DSU dsu(n + 1);
  for (; m; --m) {
    int z, x, y;
    std::cin >> z >> x >> y;
    if (z == 1) {
      dsu.unite(x, y);
    } else {
      std::cout << (dsu.find(x) == dsu.find(y) ? 'Y' : 'N') << '\n';
    }
  }
  return 0;
}

class Dsu:
    def __init__(self, size):
        self.pa = list(range(size))
        self.size = [1] * size

    def find(self, x):
        if self.pa[x] != x:
            self.pa[x] = self.find(self.pa[x])
        return self.pa[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.pa[y] = x
        self.size[x] += self.size[y]


if __name__ == "__main__":
    n, m = map(int, input().split())
    dsu = Dsu(n + 1)
    for _ in range(m):
        z, x, y = map(int, input().split())
        if z == 1:
            dsu.unite(x, y)
        else:
            print("Y" if dsu.find(x) == dsu.find(y) else "N")

Độ phức tạp

Sau khi sử dụng cả nén đường đi và hợp nhất heuristic, thời gian trung bình cho mỗi thao tác DSU chỉ là \(O(\alpha(n))\). Trong đó, \(\alpha\) là hàm ngược của hàm Ackermann, tăng trưởng cực kỳ chậm. Điều này có nghĩa là, thời gian chạy trung bình của một thao tác DSU có thể được coi là một hằng số rất nhỏ. Chứng minh độ phức tạp thời gian nằm ở trang này.

Hàm Ackermann ngược

Định nghĩa của hàm Ackermann \(A(m, n)\) là:

\(A(m, n) = \begin{cases}n+1&\text{if }m=0\\A(m-1,1)&\text{if }m>0\text{ and }n=0\\A(m-1,A(m,n-1))&\text{otherwise}\end{cases}\)

Và hàm Ackermann ngược \(\alpha(n)\) được định nghĩa là số nguyên lớn nhất \(m\) sao cho \(A(m, m) \leqslant n\).

Độ phức tạp không gian của DSU rõ ràng là \(O(n)\).

Thao tác mở rộng

Dựa trên DSU thông thường, có thể thực hiện một loạt các sửa đổi để hỗ trợ nhiều thao tác hơn hoặc duy trì thông tin phức tạp hơn.

DSU có hỗ trợ xóa (DSU with Deletion)

DSU thông thường không hỗ trợ thao tác xóa, vì khi xóa một nút, không thể tránh khỏi việc xóa tất cả các nút trong cây con có gốc là nút đó. Để giải quyết vấn đề này, trong DSU có hỗ trợ xóa, thông qua việc xây dựng các nút ảo (dummy nodes), ta có thể đảm bảo rằng tất cả các nút thực sự lưu trữ dữ liệu luôn là nút lá. Để làm được điều này, khi khởi tạo, cần tạo một nút ảo cho mỗi nút dữ liệu, và đặt cha của nút dữ liệu là nút ảo tương ứng. Do mỗi lần hợp nhất hai tập hợp, ta luôn nối gốc của một cây vào gốc của cây kia, mà các nút gốc đều là nút ảo, nên từ đầu đến cuối chỉ có các nút ảo mới có nút con, còn tất cả các nút lưu trữ phần tử thực tế đều không có nút con. Khi đó, việc di chuyển một phần tử trở nên dễ thực hiện hơn nhiều.

Chú ý, sau khi xóa một nút đơn lẻ, cần phải xây dựng lại một nút ảo mới làm cha của nút đó; nếu không, các thao tác hợp nhất và xóa tiếp theo sẽ không thực hiện chính xác.

Tham khảo triển khai cho bài toán mẫu SPOJ JMFILTER - Junk-Mail Filter

C++Python

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

struct DSU {
  size_t id;
  std::vector<size_t> pa, size;

  explicit DSU(size_t size_, size_t m)
      : id(size_ * 2), pa(size_ * 2 + m), size(size_ * 2 + m, 1) {
    // size 的前半段其实没有使用，只是为了让下标计算更简单
    std::iota(pa.begin(), pa.begin() + size_,
              size_);  // 令 i 指向虚点 i + size_
    std::iota(pa.begin() + size_, pa.end(), size_);  // 所有虚点指向它自身
  }

  size_t find(size_t x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }

  void unite(size_t x, size_t y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (size[x] < size[y]) std::swap(x, y);
    pa[y] = x;
    size[x] += size[y];
  }

  void erase(size_t x) {
    size_t y = find(x);
    --size[y];
    pa[x] = id++;
  }
};

int main() {
  int n, m, case_id = 0;
  while ((std::cin >> n >> m), n) {
    DSU dsu(n, m);
    for (; m; --m) {
      char ch;
      std::cin >> ch;
      if (ch == 'M') {
        int x, y;
        std::cin >> x >> y;
        dsu.unite(x, y);
      } else if (ch == 'S') {
        int x;
        std::cin >> x;
        dsu.erase(x);
      }
    }
    int res = 0;
    for (int i = n; i < dsu.id; ++i) {
      if (dsu.size[i] && i == dsu.find(i)) {
        ++res;
      }
    }
    std::cout << "Case #" << (++case_id) << ": " << res << '\n';
  }
  return 0;
}

# 此代码仅作示意，因超时无法通过原题
class Dsu:
    def __init__(self, size, m):
        self.id = size * 2
        # 令 i 指向虚点 i + size_，所有虚点指向它自身
        self.pa = list(range(size, size * 2)) + list(range(size, size * 2 + m))
        # size 的前半段其实没有使用，只是为了让下标计算更简单
        self.size = [1] * (size * 2 + m)

    def find(self, x):
        if self.pa[x] != x:
            self.pa[x] = self.find(self.pa[x])
        return self.pa[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.pa[y] = x
        self.size[x] += self.size[y]

    def erase(self, x):
        y = self.find(x)
        self.size[y] -= 1
        self.pa[x] = self.id
        self.id += 1


if __name__ == "__main__":
    case_id = 0
    while True:
        n, m = map(int, input().split())
        if not n:
            break
        dsu = Dsu(n, m)
        for _ in range(m):
            op = input().split()
            if op[0] == "M":
                x = int(op[1])
                y = int(op[2])
                dsu.unite(x, y)
            elif op[0] == "S":
                x = int(op[1])
                dsu.erase(x)
        res = 0
        for i in range(n, dsu.id):
            if dsu.size[i] and i == dsu.find(i):
                res += 1
        case_id += 1
        print(f"Case #{case_id}: {res}")
        input()

Phương pháp tương tự cũng có thể được sử dụng để thực hiện việc di chuyển một phần tử đơn lẻ giữa các tập hợp. Chi tiết triển khai xem trong ví dụ.

DSU có trọng số (Weighted DSU)

Ta cũng có thể định nghĩa một loại trọng số trên các cạnh của DSU và các phép toán tương ứng sinh ra khi nén đường đi, từ đó giải quyết nhiều vấn đề hơn. Ví dụ, đối với bài toán kinh điển "NOI2001" Chuỗi thức ăn, ta có thể duy trì phép cộng modulo \(3\) trên trọng số cạnh. Đối với các vấn đề duy trì trọng số cạnh theo modulo mà modulo rất nhỏ, ta còn có thể giải quyết bằng cách tách một điểm trong DSU thành nhiều trạng thái. Kỹ thuật đặc biệt này cũng được gọi là "DSU theo loại" (Species DSU) hoặc "DSU miền mở rộng". Phần sau sẽ dùng ví dụ để minh họa các cách làm này.

Để duy trì trọng số cạnh trong DSU, cần lưu trữ trọng số cạnh dưới dạng giá trị đi xuống nút con. Do đó, mỗi nút lưu trữ trọng số cạnh giữa nó và nút cha của nó. Chỉ khi nút cha của một nút thay đổi, ta mới cần điều chỉnh trọng số cạnh tương ứng. Trong trường hợp tổng quát, điều này có thể xảy ra khi nén đường đi và hợp nhất hai nút. Ví dụ, nếu trọng số cạnh là khoảng cách giữa nút hiện tại và nút cha, thì khi nén đường đi, mỗi lần thay thế nút cha hiện tại bằng nút gốc, cần cộng khoảng cách từ nút cha đến nút gốc vào trọng số cạnh được lưu trữ của nút hiện tại; tương tự, khi hợp nhất hai tập hợp nút, cần tính toán trọng số của cạnh mới nối hai nút gốc.

Tham khảo triển khai cho bài toán mẫu Library Checker - Unionfind with Potential

C++Python

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

constexpr int M = 998244353;

struct DSU {
  std::vector<size_t> pa, size, dist;

  explicit DSU(size_t size_) : pa(size_), size(size_, 1), dist(size_) {
    std::iota(pa.begin(), pa.end(), 0);
  }

  size_t find(size_t x) {
    if (pa[x] == x) return x;
    size_t y = find(pa[x]);
    (dist[x] += dist[pa[x]]) %= M;
    return pa[x] = y;
  }

  bool unite(size_t x, size_t y, int d) {
    find(x), find(y);
    (d += M - dist[y]) %= M;
    (d += dist[x]) %= M;
    x = pa[x], y = pa[y];
    if (x == y) return d == 0;
    if (size[x] < size[y]) {
      std::swap(x, y);
      d = (M - d) % M;
    }
    pa[y] = x;
    size[x] += size[y];
    dist[y] = d;
    return true;
  }

  int check(size_t x, size_t y) {
    find(x), find(y);
    if (pa[x] != pa[y]) return -1;
    return (dist[y] - dist[x] + M) % M;
  }
};

int main() {
  int n, m;
  std::cin >> n >> m;
  DSU dsu(n);
  for (; m; --m) {
    int op;
    std::cin >> op;
    if (op) {
      int u, v;
      std::cin >> u >> v;
      std::cout << dsu.check(u, v) << '\n';
    } else {
      int u, v, x;
      std::cin >> u >> v >> x;
      std::cout << dsu.unite(u, v, x) << '\n';
    }
  }
  return 0;
}

M = 998244353


class DSU:
    def __init__(self, size: int):
        self.pa = list(range(size))
        self.size = [1] * size
        self.dist = [0] * size

    def find(self, x: int) -> int:
        if self.pa[x] == x:
            return x
        y = self.find(self.pa[x])
        self.dist[x] = (self.dist[x] + self.dist[self.pa[x]]) % M
        self.pa[x] = y
        return y

    def unite(self, x: int, y: int, d: int) -> bool:
        self.find(x)
        self.find(y)
        d = (d + M - self.dist[y]) % M
        d = (d + self.dist[x]) % M
        x, y = self.pa[x], self.pa[y]
        if x == y:
            return d == 0
        if self.size[x] < self.size[y]:
            x, y = y, x
            d = (M - d) % M
        self.pa[y] = x
        self.size[x] += self.size[y]
        self.dist[y] = d
        return True

    def check(self, x: int, y: int) -> int:
        self.find(x)
        self.find(y)
        if self.pa[x] != self.pa[y]:
            return -1
        return (self.dist[y] - self.dist[x] + M) % M


if __name__ == "__main__":
    n, m = map(int, input().split())
    dsu = DSU(n)
    for _ in range(m):
        op, *rest = map(int, input().split())
        if op:
            u, v = rest
            print(dsu.check(u, v))
        else:
            u, v, x = rest
            print(int(dsu.unite(u, v, x)))

Bài tập ví dụ

Trong các cuộc thi thuật toán, các bài toán trực tiếp kiểm tra DSU đa số đều cần thiết kế cấu trúc đặc biệt cho bài toán.

UVa11987 Almost Union-Find

Triển khai một cấu trúc dữ liệu tương tự DSU, hỗ trợ các thao tác sau:

Hợp nhất tập hợp chứa hai phần tử.
Di chuyển một phần tử đơn lẻ sang tập hợp chứa một phần tử khác.
Truy vấn kích thước tập hợp chứa một phần tử và tổng các phần tử trong tập hợp đó.

Giải đáp

Trong bài toán này, thao tác 1 và 3 dễ xử lý, điểm khó là thao tác 2. Giả sử cần di chuyển phần tử \(x\) sang tập hợp chứa phần tử \(y\). Trong DSU thông thường, việc trực tiếp đặt cha của phần tử \(x\) là nút gốc của tập hợp chứa \(y\) là không được, vì điều này sẽ di chuyển tất cả các phần tử trong cây con có gốc là \(x\) cùng một lúc. Để giải quyết vấn đề này, giải pháp là đảm bảo phần tử \(x\) không có nút con. Để làm được điều này, khi xây dựng DSU, ta cho mỗi phần tử \(x\) tạo một nút ảo \(\tilde x\), và đặt cha của phần tử \(x\) trỏ đến nút ảo \(\tilde x\) tương ứng. Khi đó, khi hợp nhất hai tập hợp, vì luôn nối gốc của một cây vào gốc của cây kia, mà các nút gốc đều là nút ảo, nên chỉ có các nút ảo mới có nút con, còn tất cả các nút lưu trữ phần tử thực tế đều không có nút con. Lúc này, việc di chuyển một phần tử trở nên dễ thực hiện hơn nhiều.

Tham khảo triển khai

C++Python

#include <cassert>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

struct dsu {
  vector<size_t> pa, size, sum;

  explicit dsu(size_t size_)
      : pa(size_ * 2), size(size_ * 2, 1), sum(size_ * 2) {
    // size 与 sum 的前半段其实没有使用，只是为了让下标计算更简单
    iota(pa.begin(), pa.begin() + size_, size_);
    iota(pa.begin() + size_, pa.end(), size_);
    iota(sum.begin() + size_, sum.end(), 0);
  }

  void unite(size_t x, size_t y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (size[x] < size[y]) swap(x, y);
    pa[y] = x;
    size[x] += size[y];
    sum[x] += sum[y];
  }

  void move(size_t x, size_t y) {
    auto fx = find(x), fy = find(y);
    if (fx == fy) return;
    pa[x] = fy;
    --size[fx], ++size[fy];
    sum[fx] -= x, sum[fy] += x;
  }

  size_t find(size_t x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
};

int main() {
  size_t n, m, op, x, y;
  while (cin >> n >> m) {
    dsu dsu(n + 1);  // 元素范围是 1..n
    while (m--) {
      cin >> op;
      switch (op) {
        case 1:
          cin >> x >> y;
          dsu.unite(x, y);
          break;
        case 2:
          cin >> x >> y;
          dsu.move(x, y);
          break;
        case 3:
          cin >> x;
          x = dsu.find(x);
          cout << dsu.size[x] << ' ' << dsu.sum[x] << '\n';
          break;
        default:
          assert(false);  // not reachable
      }
    }
  }
  return 0;
}

class Dsu:
    def __init__(self, size):
        # size 与 sum 的前半段其实没有使用，只是为了让下标计算更简单
        self.pa = list(range(size, size * 2)) * 2
        self.size = [1] * size * 2
        self.sum = list(range(size)) * 2

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.pa[y] = x
        self.size[x] += self.size[y]
        self.sum[x] += self.sum[y]

    def move(self, x, y):
        fx, fy = self.find(x), self.find(y)
        if fx == fy:
            return
        self.pa[x] = fy
        self.size[fx] -= 1
        self.size[fy] += 1
        self.sum[fx] -= x
        self.sum[fy] += x

    def find(self, x):
        if self.pa[x] != x:
            self.pa[x] = self.find(self.pa[x])
        return self.pa[x]


if __name__ == "__main__":
    while True:
        try:
            n, m = map(int, input().split())
            dsu = Dsu(n + 1)  # 元素范围是 1..n
            for _ in range(m):
                op_x_y = list(map(int, input().split()))
                op = op_x_y[0]
                if op == 1:
                    dsu.unite(op_x_y[1], op_x_y[2])
                elif op == 2:
                    dsu.move(op_x_y[1], op_x_y[2])
                elif op == 3:
                    x = dsu.find(op_x_y[1])
                    print(dsu.size[x], dsu.sum[x])
        except EOFError:
            break

Luogu P2024「NOI2011」Chuỗi Thức Ăn

Vương quốc động vật có ba loại động vật \(A, B, C\), chuỗi thức ăn của ba loại này tạo thành một vòng tròn thú vị. \(A\) ăn \(B\), \(B\) ăn \(C\), \(C\) ăn \(A\).

Có \(N\) con vật, được đánh số từ \(1\) đến \(N\). Mỗi con vật thuộc một trong ba loại \(A, B, C\), nhưng ta không biết nó là loại nào.

Có người dùng hai loại phát biểu để mô tả mối quan hệ chuỗi thức ăn của \(N\) con vật này:

Phát biểu loại 1 là 1 X Y, biểu thị \(X\) và \(Y\) cùng loại.
Phát biểu loại 2 là 2 X Y, biểu thị \(X\) ăn \(Y\).

Người này nói \(K\) câu, mỗi câu là một trong hai loại trên đối với \(N\) con vật, trong số \(K\) câu này có câu đúng, có câu sai. Khi một câu thỏa mãn một trong ba điều kiện sau, câu đó là câu sai, nếu không là câu đúng:

Câu hiện tại mâu thuẫn với một số câu đúng trước đó, là câu sai;
Câu hiện tại có \(X\) hoặc \(Y\) lớn hơn \(N\), là câu sai;
Câu hiện tại biểu thị \(X\) ăn \(X\), là câu sai.

Nhiệm vụ của bạn là dựa vào \(N\) và \(K\) câu đã cho, xuất ra tổng số câu sai.

Giải đáp 1

Cân nhắc sử dụng DSU có trọng số để duy trì thông tin chuỗi thức ăn. Nếu \(x\) và \(y\) cùng loại, thì \(x\equiv y\pmod 3\); nếu \(x\) ăn \(y\), thì \(x - y \equiv 1 \pmod 3\). Như vậy bài toán này được quy về bài toán mẫu ở phần trước.

Cụ thể, đối với mỗi câu, loại trừ những câu sai hiển nhiên như \(x>n\) hoặc \(y>n\), cần phán đoán \(x\) và \(y\) đã được kết nối hay chưa: nếu đã kết nối, tính toán khoảng cách modulo của chúng và so sánh với thông tin mà câu này tuyên bố; nếu chưa, kết nối hai nút theo thông tin mà câu này cung cấp. Ngoài các trường hợp hiển nhiên, một câu là câu sai khi và chỉ khi hai nút được đề cập đã được kết nối và khoảng cách tương ứng mâu thuẫn với thông tin mà câu này tuyên bố.

Tham khảo triển khai 1

C++Python

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

constexpr int M = 3;

struct DSU {
  std::vector<size_t> pa, size, dist;

  explicit DSU(size_t size_) : pa(size_), size(size_, 1), dist(size_) {
    std::iota(pa.begin(), pa.end(), 0);
  }

  size_t find(size_t x) {
    if (pa[x] == x) return x;
    size_t y = find(pa[x]);
    (dist[x] += dist[pa[x]]) %= M;
    return pa[x] = y;
  }

  bool unite(size_t x, size_t y, int d) {
    find(x), find(y);
    (d += M - dist[y]) %= M;
    (d += dist[x]) %= M;
    x = pa[x], y = pa[y];
    if (x == y) return d == 0;
    if (size[x] < size[y]) {
      std::swap(x, y);
      d = (M - d) % M;
    }
    pa[y] = x;
    size[x] += size[y];
    dist[y] = d;
    return true;
  }
};

int main() {
  int n, m;
  std::cin >> n >> m;
  DSU dsu(n + 1);
  int res = 0;
  for (; m; --m) {
    int op, x, y;
    std::cin >> op >> x >> y;
    if (x > n || y > n)
      ++res;
    else
      res += !dsu.unite(x, y, op == 1 ? 0 : 1);
  }
  std::cout << res << std::endl;
  return 0;
}

M = 3


class DSU:
    def __init__(self, size: int):
        self.pa = list(range(size))
        self.size = [1] * size
        self.dist = [0] * size

    def find(self, x: int) -> int:
        if self.pa[x] == x:
            return x
        y = self.find(self.pa[x])
        self.dist[x] = (self.dist[x] + self.dist[self.pa[x]]) % M
        self.pa[x] = y
        return y

    def unite(self, x: int, y: int, d: int) -> bool:
        self.find(x)
        self.find(y)
        d = (d + M - self.dist[y]) % M
        d = (d + self.dist[x]) % M
        x, y = self.pa[x], self.pa[y]
        if x == y:
            return d == 0
        if self.size[x] < self.size[y]:
            x, y = y, x
            d = (M - d) % M
        self.pa[y] = x
        self.size[x] += self.size[y]
        self.dist[y] = d
        return True


if __name__ == "__main__":
    n, m = map(int, input().split())
    dsu = DSU(n + 1)
    res = 0
    for _ in range(m):
        op, x, y = map(int, input().split())
        if x > n or y > n:
            res += 1
        else:
            res += not dsu.unite(x, y, 0 if op == 1 else 1)
    print(res)

Giải đáp 2

Tách một loài vật \(x\) thành ba trạng thái. Trong triển khai cụ thể, ta có thể coi các trạng thái khác nhau là các phần tử khác nhau:

Trạng thái cùng tập hợp với \(x\) có nghĩa là \(x\) cùng loài;
Trạng thái cùng tập hợp với \(x+n\) có nghĩa là \(x\) bị ăn bởi;
Trạng thái cùng tập hợp với \(x+2n\) có nghĩa là ăn \(x\).

Vậy, đối với một câu:

1 x y là câu sai khi và chỉ khi:
1. \(x>N\) hoặc \(y>N\);
2. \(y\) cùng tập hợp với \(x+n\) hoặc \(x+2n\).
2 x y là câu sai khi và chỉ khi:
1. \(x>N\) hoặc \(y>N\);
2. \(y\) cùng tập hợp với \(x\) hoặc \(x+2n\).
Nếu là câu đúng, hợp nhất các trạng thái tương ứng.

Tham khảo triển khai 2

C++Python

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

struct DSU {
  std::vector<size_t> pa, size;

  explicit DSU(size_t size_) : pa(size_), size(size_, 1) {
    std::iota(pa.begin(), pa.end(), 0);
  }

  size_t find(size_t x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }

  void unite(size_t x, size_t y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (size[x] < size[y]) std::swap(x, y);
    pa[y] = x;
    size[x] += size[y];
  }
};

int main() {
  int n, m;
  std::cin >> n >> m;
  DSU dsu(n * 3 + 1);
  int res = 0;
  for (; m; --m) {
    int op, x, y;
    std::cin >> op >> x >> y;
    if (x > n || y > n)
      ++res;
    else if (op == 1) {
      if (dsu.find(x) == dsu.find(y + n) ||
          dsu.find(x) == dsu.find(y + (n << 1))) {
        ++res;
      } else {
        dsu.unite(x, y);
        dsu.unite(x + n, y + n);
        dsu.unite(x + n * 2, y + n * 2);
      }
    } else {
      if (dsu.find(x) == dsu.find(y) || dsu.find(x) == dsu.find(y + n)) {
        ++res;
      } else {
        dsu.unite(x, y + n * 2);
        dsu.unite(x + n, y);
        dsu.unite(x + n * 2, y + n);
      }
    }
  }
  std::cout << res << std::endl;
  return 0;
}

class Dsu:
    def __init__(self, size):
        self.pa = list(range(size))
        self.size = [1] * size

    def find(self, x):
        if self.pa[x] != x:
            self.pa[x] = self.find(self.pa[x])
        return self.pa[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.pa[y] = x
        self.size[x] += self.size[y]


if __name__ == "__main__":
    n, m = map(int, input().split())
    dsu = Dsu(n * 3 + 1)
    res = 0
    for _ in range(m):
        op, x, y = map(int, input().split())
        if x > n or y > n:
            res += 1
        elif op == 1:
            if dsu.find(x) == dsu.find(y + n) or dsu.find(x) == dsu.find(y + (n << 1)):
                res += 1
            else:
                dsu.unite(x, y)
                dsu.unite(x + n, y + n)
                dsu.unite(x + n * 2, y + n * 2)
        else:
            if dsu.find(x) == dsu.find(y) or dsu.find(x) == dsu.find(y + n):
                res += 1
            else:
                dsu.unite(x, y + n * 2)
                dsu.unite(x + n, y)
                dsu.unite(x + n * 2, y + n)
    print(res)

ABC396E Min of Restricted Sum

Cho các số nguyên \(N, M\) và các dãy số nguyên có độ dài \(M\): \(X=(X_1,X_2,\ldots,X_M)\)、\(Y=(Y_1,Y_2,\ldots,Y_M)\)、\(Z=(Z_1,Z_2,\ldots,Z_M)\). Trong đó, đảm bảo tất cả các phần tử của \(X\) và \(Y\) đều nằm trong phạm vi \(1\) đến \(N\).

Dãy số nguyên không âm có độ dài \(N\), \(A=(A_1,A_2,\ldots,A_N)\), được định nghĩa là dãy số nguyên tốt khi và chỉ khi thỏa mãn điều kiện sau:

Với mọi số nguyên \(i\) thỏa mãn \(1 \leq i \leq M\), có \(A_{X_i} \oplus A_{Y_i} = Z_i\), trong đó \(\oplus\) biểu thị phép toán XOR.

Hãy phán đoán xem có tồn tại dãy số nguyên tốt như vậy không. Nếu tồn tại, hãy tìm dãy số nguyên tốt sao cho tổng các phần tử \(\displaystyle \sum_{i=1}^N A_i\) là nhỏ nhất, và xuất ra dãy đó.

Giải đáp

Phép toán XOR chính là quan hệ "giống nhau" hay "khác nhau" trên từng bit nhị phân. Vậy, tách tất cả các bit của \(A_i\) ra, quan hệ XOR có thể được duy trì bằng DSU có trọng số (hoặc DSU theo loại). Khi tính tổng, các phần tử trong cùng một thành phần liên thông thường được chia thành hai nhóm, giữa hai nhóm này cần có giá trị khác nhau, chỉ cần gán giá trị 0 cho nhóm có giá trị lớn hơn và 1 cho nhóm còn lại là đảm bảo tổng trọng số nhỏ nhất.

Tham khảo triển khai

C++Python

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

constexpr int M = 2;

struct DSU {
  std::vector<size_t> pa, size, dist;

  explicit DSU(size_t size_) : pa(size_), size(size_, 1), dist(size_) {
    std::iota(pa.begin(), pa.end(), 0);
  }

  size_t find(size_t x) {
    if (pa[x] == x) return x;
    size_t y = find(pa[x]);
    (dist[x] += dist[pa[x]]) %= M;
    return pa[x] = y;
  }

  bool unite(size_t x, size_t y, int d) {
    find(x), find(y);
    (d += M - dist[y]) %= M;
    (d += dist[x]) %= M;
    x = pa[x], y = pa[y];
    if (x == y) return d == 0;
    if (size[x] < size[y]) {
      std::swap(x, y);
      d = (M - d) % M;
    }
    pa[y] = x;
    size[x] += size[y];
    dist[y] = d;
    return true;
  }
};

int main() {
  int n, m;
  std::cin >> n >> m;
  DSU dsu((n + 1) << 5);
  for (; m; --m) {
    int x, y, z;
    std::cin >> x >> y >> z;
    for (int i = 0; i < 31; ++i) {
      if (!dsu.unite((x << 5) | i, (y << 5) | i, (z >> i) & 1)) {
        std::cout << -1 << std::endl;
        return 0;
      }
    }
  }
  std::vector<int> a(n + 1), cnt((n + 1) << 5);
  for (int i = 1; i < ((n + 1) << 5); ++i) {
    dsu.find(i);
    if (dsu.dist[i]) ++cnt[dsu.pa[i]];
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < 31; ++j) {
      int x = (i << 5) | j, y = dsu.pa[x];
      if ((cnt[y] > dsu.size[y] / 2) ^ dsu.dist[x]) {
        a[i] |= 1 << j;
      }
    }
  }
  for (int i = 1; i <= n; ++i) std::cout << a[i] << ' ';
  std::cout << std::endl;
  return 0;
}

M = 2


class DSU:
    def __init__(self, size: int):
        self.pa = list(range(size))
        self.size = [1] * size
        self.dist = [0] * size

    def find(self, x: int) -> int:
        if self.pa[x] == x:
            return x
        y = self.find(self.pa[x])
        self.dist[x] = (self.dist[x] + self.dist[self.pa[x]]) % M
        self.pa[x] = y
        return y

    def unite(self, x: int, y: int, d: int) -> bool:
        self.find(x)
        self.find(y)
        d = (d + M - self.dist[y]) % M
        d = (d + self.dist[x]) % M
        x, y = self.pa[x], self.pa[y]
        if x == y:
            return d == 0
        if self.size[x] < self.size[y]:
            x, y = y, x
            d = (M - d) % M
        self.pa[y] = x
        self.size[x] += self.size[y]
        self.dist[y] = d
        return True


if __name__ == "__main__":
    n, m = map(int, input().split())
    dsu = DSU((n + 1) << 5)
    for _ in range(m):
        x, y, z = map(int, input().split())
        for i in range(31):
            if not dsu.unite((x << 5) | i, (y << 5) | i, (z >> i) & 1):
                print(-1)
                exit()

    a = [0] * (n + 1)
    cnt = [0] * ((n + 1) << 5)

    for i in range(1, (n + 1) << 5):
        dsu.find(i)
        if dsu.dist[i]:
            cnt[dsu.pa[i]] += 1

    for i in range(1, n + 1):
        for j in range(31):
            x = (i << 5) | j
            y = dsu.pa[x]
            if (cnt[y] > dsu.size[y] // 2) ^ dsu.dist[x]:
                a[i] |= 1 << j

    print(" ".join(map(str, a[1:])))

Bài tập thực hành

Các ứng dụng khác

Thuật toán Kruskal trong Thuật toán cây bao trùm nhỏ nhất và thuật toán Tarjan trong Tổ tiên chung gần nhất đều là các thuật toán dựa trên DSU.

Xem các chuyên đề liên quan tại Ứng dụng của DSU.

Tài liệu tham khảo và Đọc thêm

Trả lời trên Zhihu: Có thực sự tối ưu hóa nén đường đi hai lần trong DSU không?
Gabow, H. N., & Tarjan, R. E. (1985). A Linear-Time Algorithm for a Special Case of Disjoint Set Union. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 30, 209-221.PDF
CSDN: DSU miền mở rộng & DSU có trọng số

Tarjan, R. E., & Van Leeuwen, J. (1984). Worst-case analysis of set union algorithms. Journal of the ACM (JACM), 31(2), 245-281.ResearchGate PDF ↩
Yao, A. C. (1985). On the expected performance of path compression algorithms.SIAM Journal on Computing, 14(1), 129-133. ↩

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply