并查集（Union-Find）是一種數據結構，它提供了處理一些不交集的合并及查詢問題的高效方法。并查集主要支持兩種操作：
查找（Find）：確定某個元素屬于哪個子集，這通常意味著找到該子集的“代表元素”或“根元素”。
合并（Union）：將兩個子集合并成一個集合。
并查集通過數組或樹形結構來實現，其中每個節點指向其父節點，根節點指向自身，這樣形成一個或多個樹形結構。每棵樹代表一個集合，樹根的標識符（通常是數組的索引）代表整個集合的標識符。
基本概念：
初始化：開始時，每個元素各自構成一個單元素集合，即每個元素的父節點是其自身。
路徑壓縮：在執行查找操作時，將查找路徑上的每個節點直接連接到根節點，這樣可以加快后續查找的速度。
按秩合并：合并時，總是將更小的樹連接到更大的樹的根節點上，這可以幫助避免樹變得過深，從而保持操作的效率。
并查集的重要思想在于，用集合中的一個元素代表集合。
現在1號和3號比武，假設1號贏了（這里具體誰贏暫時不重要），那么3號就認1號作幫主（合并1號和3號所在的集合，1號為代表元素）。
現在2號想和3號比武（合并3號和2號所在的集合），但3號表示，別跟我打，讓我幫主來收拾你（合并代表元素）。不妨設這次又是1號贏了，那么2號也認1號做幫主。
上面大概介紹完了整體的東西下面介紹一下細節：
下面是代碼部分：
// 查找i的代表元素，并進行路徑壓縮優化
int find(int i) {if (fa[i] == i) // 如果元素i指向自己，那么它是代表元素return i;elsereturn fa[i] = find(fa[i]); // 否則遞歸查找，并更新i的父鏈接為代表元素
}// 合并i和j所在的集合
void unionn(int i, int j) {int i_fa = find(i); // 查找i的代表元素int j_fa = find(j); // 查找j的代表元素fa[i_fa] = j_fa; // 將i的集合合并到j的集合中
}
find 函數通過遞歸查找找到一個元素的代表元素，并在查找的過程中將元素直接鏈接到代表元素，這個優化叫做路徑壓縮，它可以減少后續查找的時間。
unionn 函數將兩個元素所在的集合合并成一個集合。它首先找到每個元素的代表元素，然后將其中一個集合的代表元素鏈接到另一個集合的代表元素上，從而完成合并。這里沒有實現按秩合并或路徑壓縮的更復雜的優化。
下面是一道題
public class UnionFind {private int[] parent;public UnionFind(int n) {parent = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;}}public int find(int x) {if (x != parent[x]) {parent[x] = find(parent[x]);}return parent[x];}public void union(int x, int y) {parent[find(x)] = find(y);}public boolean isConnected(int x, int y) {return find(x) == find(y);}public static void main(String[] args) {UnionFind uf = new UnionFind(10);uf.union(0, 1); // Marry person 1 and 2uf.union(2, 3); // Marry person 3 and 4boolean areMarried = uf.isConnected(1, 4); // Check if person 2 and 5 are relatedSystem.out.println(areMarried ? "YES" : "NO"); // Output should be "NO" if unrelated}
}
