并查集的核心思想

并查集主要由兩個操作構成：

• Find：查找某個元素所在集合的根節點。并查集的特點是，每個元素都指向它自己的父節點，根節點的父節點指向它自己。查找過程中可以通過路徑壓縮來加速后續的查找操作，即將路徑上所有節點直接指向根節點。

• Union：將兩個集合合并。如果兩個元素屬于不同的集合，我們將它們的集合合并起來。為了提高效率，我們可以使用按秩合并（將樹較矮的集合合并到樹較高的集合下）。

問題描述

思路分析

在這個問題中，我們可以將每個人視為一個節點，朋友關系視為連通關系，判斷兩個人是否是朋友其實就是判斷他們是否屬于同一組。通過并查集，我們可以高效地實現這兩種操作：合并操作（Union）和查找操作（Find）。

1. 查找操作：對于一個給定的節點，我們需要找到它的根節點，也就是它所在集合的代表元素。通過路徑壓縮的技巧，我們能夠在查找過程中將路徑上的所有節點直接指向根節點，從而減少后續查詢的時間復雜度。

2. 合并操作：當兩個節點屬于不同的集合時，我們需要將它們合并為一個集合。為了保證合并操作的效率，我們使用了按秩合并的策略，即將樹矮的集合合并到樹高的集合下，這樣可以盡可能減少樹的高度，提高查詢效率。

解決步驟

1. 初始化：首先我們創建一個大小為 n+1 的數組 parent，用于存儲每個節點的父節點。在初始化時，每個節點的父節點都指向自己，表示每個節點是獨立的。

2. 操作解析：

   • 對于 op == 1 的操作，表示將兩個節點 x 和 y 連接成一個集合。我們通過調用 union(x, y) 來合并它們的集合。
   • 對于 op == 2 的操作，表示查詢兩個節點 x 和 y 是否屬于同一集合。我們通過調用 find(x) 和 find(y) 來查詢它們的根節點，如果根節點相同，則表示它們是朋友關系。

3. 路徑壓縮與按秩合并：

   • 在 find 操作中，我們使用了路徑壓縮技術。每次查找時，我們都將路徑上的所有節點直接指向根節點，這樣可以有效減少查找時的時間復雜度。
   • 在 union 操作中，我們使用按秩合并的策略，通過比較兩個集合的大小，將較小的集合合并到較大的集合中，從而保證了合并操作的效率。

---

代碼：

import java.util.Scanner;// 1:無需package
// 2: 類名必須Main, 不可修改public class Main {private static int[] parent;public static void main(String[] args) {//思想：維護一個數組將每個元素的朋友記錄在里面，一個查找函數，一個合并函數Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();parent = new int[n + 1];// 初始化，每個節點的父節點指向自己for (int i = 1; i <= n; i++) {parent[i] = i;}for (int i = 0; i < m; i++) {int op = sc.nextInt();int x = sc.nextInt();int y = sc.nextInt();if (op == 1) {union(x, y);} else {System.out.println(find(x) == find(y) ? "YES" : "NO");}}}// 路徑壓縮的查找public static int find(int i) {// 我們需要找到該元素的根節點，先假設當前元素為根節點，//這個函數用來查找根節點，而根節點的父節點等于他自己，parent[root]=rootif (i != parent[i]) {parent[i] = find(parent[i]);}return parent[i];}// 合并優化public static void union(int x, int y) {//將兩個元素的父節，若是不同則需統一，統一不需要，由我們自定義誰成為父節點，一直按照這個規矩下去int rootx = find(x);int rooty = find(y);//如果父節點不同就需要操作，相同就不需要if (rooty != rootx) {parent[rooty] = rootx;}}
}