โปรแกรม C++ ใช้งานโครงสร้างข้อมูล Disjoint Set

Disjoint set คือกลุ่มของเซตที่ไม่มีรายการใดอยู่ในเซตมากกว่าหนึ่งเซต รองรับการดำเนินการ union และ find บนเซตย่อย

Find(): ใช้หาว่าองค์ประกอบใดอยู่ในเซตย่อยไหน และคืนค่าตัวแทนของเซตนั้น

Union(): รวมเซตย่อยสองเซตเป็นเซตเดียว และตัวแทนของเซตหนึ่งจะกลายเป็นตัวแทนของอีกเซต

ฟังก์ชันและ Pseudocode

Begin
  สมมติ k คือองค์ประกอบ
  makeset(k):
    k.parent = k
  Find(x):
    If k.parent == k
      return k
    else
      return Find(k.parent)
  Union(a, b):
    รับเซต a และ b สองเซต
    aroot = Find(a)
    broot = Find(b)
    aroot.parent = broot
End

ตัวอย่างโค้ด

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class DisjointSet {
  unordered_map<int, int> parent;
public:
  void makeSet(vector<int> const &wholeset) {
    for (int i : wholeset)
      parent[i] = i;
  }
  int Find(int l) {
    if (parent[l] == l)
      return l;
    return Find(parent[l]);
  }
  void Union(int m, int n) {
    int x = Find(m);
    int y = Find(n);
    parent[x] = y;
  }
};

void print(vector<int> const &universe, DisjointSet &dis) {
  for (int i : universe)
    cout << dis.Find(i) << " ";
  cout << '\n';
}

int main() {
  vector<int> wholeset = { 6, 7, 1, 2, 3 };
  DisjointSet dis;
  dis.makeSet(wholeset);
  dis.Union(7, 6);
  print(wholeset, dis);
  if (dis.Find(7) == dis.Find(6))
    cout << "Yes" << endl;
  else
    cout << "No";
  if (dis.Find(3) == dis.Find(4))
    cout << "Yes" << endl;
  else
    cout << "No";
  return 0;
}

ผลลัพธ์

6 6 1 2 3
Yes
No