普通并查集

  1. class UnionFind {
  2.     vector<int> f;
  3.     vector<int> cnt;
  4.     int n;
  5. public:
  6.     UnionFind(int n) : n(n) {
  7.         f.resize(n);
  8.         cnt.resize(n);
  9.         for (int i = 0; i < n; i++) {
  10.             f[i] = i;
  11.             cnt[i] = 1;
  12.         }
  13.     }
  14.     int find(int x) {
  15.         return f[x] == x ? x : f[x] = find(f[x]);
  16.     }
  17.     void unite(int x, int y) {
  18.         x = find(x);
  19.         y = find(y);
  20.         if (x == y) return;
  21.         f[x] = y;
  22.         cnt[y] += cnt[x];
  23.     }
  24.     bool same(int x, int y) {
  25.         return find(x) == find(y);
  26.     }
  27.     int getCnt(int x) {
  28.         return cnt[x];
  29.     }
  30. };
  1. class UnionFind:
  2.     def __init__(self, n):
  3.         self.parent = [i for i in range(n)]
  4.         self.rank = [0 for i in range(n)]
  5.     def find(self, x):
  6.         if self.parent[x] == x:
  7.             return x
  8.         else:
  9.             self.parent[x] = self.find(self.parent[x])
  10.             return self.parent[x]
  11.     def union(self, x, y):
  12.         x = self.find(x)
  13.         y = self.find(y)
  14.         if self.rank[x] > self.rank[y]:
  15.             self.parent[y] = x
  16.         else:
  17.             self.parent[x] = y
  18.             if self.rank[x] == self.rank[y]:
  19.                 self.rank[y] += 1
  20.     def same(self, x, y):
  21.         return self.find(x) == self.find(y)