【并查集1】并查集模板

2025年3月8日米哈游机试第三题也可以使用并查集解决

一、并查集是什么？

并查集（Union-Find）是一种树型数据结构，它的作用是管理元素所属集合的数据结构，主要支持两个操作：

• 合并（Union）：将两个不同的集合合并成一个集合。
• 查询（Find）：查询某个元素属于哪个集合。

从代码实现来说：

• 并查集是一个森林，每一棵树是一个集合。
• 查询是找元素所在树的根节点。
• 合并是把一个树的根节点成为另一个树的根节点的子节点。

二、数据结构实现原理：

并查集通常使用数组实现：

• 使用一个数组parent来表示每个元素的父节点。每个集合由一个代表（根节点）表示。
• 如果某个元素的父节点是自身（即parent[i] = i），则该元素是集合的代表（根节点）。

例如，初始情况：

元素：1 2 3 4
父亲：1 2 3 4

三、代码结合说明（以Python为例）：

（1）初始化：

def init(n):
    return [i for i in range(n+1)]

例如调用init(4):

• 初始parent数组为：[0, 1, 2, 3, 4] (下标0未用，元素1-4为独立集合)

（2）查找操作（路径压缩）：

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])  # 路径压缩
    return parent[x]

路径压缩 的作用：

• 当查找某个节点的根节点时，直接将该节点挂在根节点下面，这样能减少后续查询的复杂度。

示例说明：

• x → y 表示 parent[x] = y
• 假设集合结构：1→2→3，此时查询1的根，路径压缩前是1→2→3，路径压缩后变为：

1 → 3  
2 → 3

查询效率明显提升。

（3）合并操作：

def union(parent, x, y):
    root_x = find(parent, x)
    root_y = find(parent, y)
    if root_x != root_y:
        parent[root_x] = root_y  # 将x的根节点连到y的根节点下

示例说明：

• 假设集合结构：1→1,2→2,3→1，执行union(2,3)后集合变为：

1 → 1
2 → 1
3 → 1

四、并查集使用技巧总结：

• 路径压缩优化：在查询(find)过程中，让树的结构更加扁平化，大大提升了查询和合并的效率。
• 并查集的平均复杂度为$O(log_{2}N)$，性能优秀。

五、适用场景：

并查集特别适用于以下场景：

• 判断两个元素是否属于同一集合或群组（如好友关系、网络连接性等）。
• 动态计算图中联通块数量。
• 快速实现“分组”操作，如“好友圈”问题。

六、具体代码实现：

Python代码：

# 初始化
def init(n):
    return [i for i in range(n+1)]

# 查找（路径压缩）
def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

# 合并
def union(parent, x, y):
    x_root = find(parent, x)
    y_root = find(parent, y)
    if x_root != y_root:
        parent[x_root] = y_root

# 主函数
n, m = map(int, input().split())
parent = init(n)

for _ in range(m):
    z, x, y = map(int, input().split())
    if z == 1:
        union(parent, x, y)
    else:
        print("Y" if find(parent, x) == find(parent, y) else "N")

Java代码：

import java.util.Scanner;

public class Main {
    static int[] parent;

    static void init(int n) {
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    }

    static int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]); // 路径压缩
        return parent[x];
    }

    static void union(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);
        if (xRoot != yRoot)
            parent[xRoot] = yRoot;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        init(n);
        for (int i = 0; i < m; i++) {
            int z = sc.nextInt(), x = sc.nextInt(), y = sc.nextInt();
            if (z == 1) {
                union(x, y);
            } else {
                System.out.println(find(x) == find(y) ? "Y" : "N");
            }
        }
        sc.close();
    }
}

C++代码：

#include <iostream>
using namespace std;

int parent[100005];

// 初始化
void init(int n) {
    for (int i = 1; i <= n; ++i)
        parent[i] = i;
}

// 查找（路径压缩）
int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

// 合并
void unionSet(int x, int y) {
    int xRoot = find(x);
    int yRoot = find(y);
    if (xRoot != yRoot)
        parent[xRoot] = yRoot;
}

int main() {
    int n, m, z, x, y;
    cin >> n >> m;
    init(n);
    for (int i = 0; i < m; i++) {
        cin >> z >> x >> y;
        if (z == 1) {
            unionSet(x, y);
        } else {
            if (find(x) == find(y))
                cout << "Y\n";
            else
                cout << "N\n";
        }
    }
    return 0;
}

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 $N,M$ ,表示共有 $N$ 个元素和 $M$个操作。

接下来 $M$ 行，每行包含三个整数 $Z_i,X_i,Y_i$ 。

1. 当 $Z_i=1$ 时，将 $X_i$ 与 $Y_i$ 所在的集合合并。
2. 当 $Z_i=2$ 时，输出 $X_i$ 与 $Y_i$ 是否在同一集合内，是的输出 Y ；否则输出 N 。

$1<=N,M<=10^5$

输出格式

对于每一个 $Z_i=2$ 的操作，都有一行输出，每行包含一个大写字母，为 $Y$ 或者 $N$ 。

样例

样例输入

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

样例输出

N
Y
N
Y