并查集基础

引入

一、围棋的棋子有黑色和白色两种，相同颜色的棋子如果是上下或左右相邻的，则称这两个棋子是连通的，直接或间接连通的棋子称为一块棋。

现在你想开发一个围棋游戏，实时计算每个落棋子的连通信息作为AI的重要参考数据。

二、市政府 "村村通工程" 的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？

一、并查集基础概念

1.1 什么是并查集

并查集（Union-Find Set，简称UFS）是一种用于管理元素所属集合的数据结构，支持两种主要操作：

合并（Union）：将两个不同的集合合并为一个集合
查询（Find）：查询某个元素属于哪个集合，通常是判断两个元素是否属于同一集合

并查集的核心思想是用树形结构表示集合，每个集合是一棵树，树中的所有节点都属于同一个集合。树的根节点作为集合的代表元素，用于标识该集合。

并查集被很多OIer认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。

并查集的特点

操作简单高效，近乎O(1)的时间复杂度（使用路径压缩和按秩合并优化后）
主要解决元素的分组问题和连通性问题
不支持集合的分裂操作（只能合并，不能分割）
不直接支持查询集合的全部元素（需要额外维护）

并查集的数据结构表示

并查集通常使用一个数组（或者映射表）来表示，数组的索引表示元素，数组的值表示该元素的父节点：

parent[i] = j  // 表示元素i的父节点是j

如果元素是自己的父节点（即 parent[i] = i），则该元素是所在集合的根节点。

并查集的应用场景

并查集在许多问题中都有广泛应用，特别是涉及到元素分组和连通性的问题：

网络连接问题：判断网络中的节点是否连通
社交网络中的朋友圈：确定哪些人属于同一个朋友圈
等价类划分：将具有等价关系的元素划分到同一组
最小生成树算法：Kruskal算法中使用并查集判断是否形成环
图像分割：将图像中相似的区域划分为同一组
动态连通性问题：维护图中节点的连通关系，支持动态添加边

在信息学竞赛中，并查集是一种基础且重要的数据结构，掌握它对解决许多图论和集合问题至关重要。

二、并查集基本操作

2.1 初始化操作

在使用并查集之前，我们需要先进行初始化。初始化的目的是创建n个单元素集合，每个元素各自形成一个集合，自己是自己的父节点（即自己是集合的根节点）。

// 初始化并查集
void init(int n) {
    for (int i = 1; i <= n; i++) {
        parent[i] = i;  // 每个元素的父节点初始化为自己
    }
}

初始化后，并查集的结构如下图所示：

初始状态：每个元素各自为一个集合
1   2   3   4   5   ...   n
↑   ↑   ↑   ↑   ↑        ↑
1   2   3   4   5        n

2.2 查找(Find)操作

查找操作的目的是查询元素x所属的集合，具体实现是查找x所在树的根节点。根节点的特点是父节点是自己。

最基本的查找操作实现如下：

// 查找元素x所属的集合（找到x的根节点）
int find(int x) {
    if (parent[x] == x) {
        return x;  // 如果x是根节点，直接返回x
    } else {
        return find(parent[x]);  // 否则递归查找x的父节点
    }
}

这个基本实现是一个简单的递归过程：如果x是根节点（即parent[x] == x），则返回x；否则，递归查找x的父节点的根节点。

2.3 合并(Union)操作

合并操作的目的是将两个不同的集合合并为一个集合。具体实现是先找到两个元素所在集合的根节点，然后将其中一个根节点的父节点设置为另一个根节点。

最基本的合并操作实现如下：

// 合并元素x和y所属的集合
void unionSets(int x, int y) {
    int rootX = find(x);  // 找到x的根节点
    int rootY = find(y);  // 找到y的根节点
    
    if (rootX != rootY) {  // 如果x和y不在同一个集合中
        parent[rootX] = rootY;  // 将x的根节点的父节点设为y的根节点
    }
}

合并前后的结构变化示例：

合并前：两个独立的集合
集合1：       集合2：
  1             4
 / \            / \
2   3          5   6

合并后（将集合1合并到集合2）：
       4
      / \
     5   6
         \
          1
         / \
        2   3

2.4 简单实现与示例

下面是一个完整的并查集基本实现：

const int MAXN = 10005;
int parent[MAXN];

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

// 查找元素x所属的集合（找到x的根节点）
int find(int x) {
    if (parent[x] == x) {
        return x;
    } else {
        return find(parent[x]);
    }
}

// 合并元素x和y所属的集合
void unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    
    if (rootX != rootY) {
        parent[rootX] = rootY;
    }
}

// 判断元素x和y是否在同一个集合中
bool isSameSet(int x, int y) {
    return find(x) == find(y);
}

三、示例：连通性问题

以洛谷P3367【模板】并查集为例，我们需要实现合并和查询操作：

#include <iostream>
using namespace std;

const int MAXN = 10005;
int parent[MAXN];

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

// 查找元素x所属的集合（找到x的根节点）
int find(int x) {
    if (parent[x] == x) {
        return x;
    } else {
        return find(parent[x]);
    }
}

// 合并元素x和y所属的集合
void unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    
    if (rootX != rootY) {
        parent[rootX] = rootY;
    }
}

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

这个基本实现虽然正确，但在处理大规模数据时效率较低。在下一节中，我们将介绍如何优化并查集，使其在处理大规模数据时也能保持高效。

*学习笔记

暂没有学习笔记，快来抢first blood ！

引入​

一、并查集基础概念​

1.1 什么是并查集​

并查集的特点​

并查集的数据结构表示​

并查集的应用场景​

二、并查集基本操作​

2.1 初始化操作​

2.2 查找(Find)操作​

2.3 合并(Union)操作​

2.4 简单实现与示例​

三、示例：连通性问题​

*学习笔记​

引入