【数据结构】基础并查集

【数据结构】并查集

一.概述

1.定义

并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。¹

2.使用原因

已知 $A-B,C-D,A-D,E-F$ 分别有父子关系，要求给出一个字母，求出他的父节点。

在一般情况下，可以通过建单向图的方式来存储，访问时向上查找。在数据规模较小时，该方法可行，但当数据较大时( 10 5 ≤ N N o d e , 10 5 ≤ K 访问次数 10^5 \\le N_{Node},10^5 \\le K_{访问次数} 105≤NNode​,105≤K访问次数​)，最坏情况会使复杂度到达 10 5 ∗ 10 5 = 10 10 10^5*10^5=10^{10} 105∗105=1010，导致超时。分析以上思路，不难发现总是有一些路径，每次寻找时都被遍历一遍，优化这些不必要的遍历，可以降低复杂度。并查集也就应运而生。

二.原理

并查集，有“并”与“查两个部分”。

3.0.并查集的初始化

对于一个并查集，首先创建一个数组$f[N]$用来存储每一个点的根节点。在不知道初始关系时，将每一个节点对应的根节点设为他自己

3.1.并查集的查找

对于并查集的查找，通常使用函数递归实现。

基本思路：若当前节点编号$x$与$f[x]$不相同时，查找$f[x]$的节点，递归直到$x=f[x]$，返回$f[x]$或$x$。

const int N = 1e5+5;int f[N]; //并查集数组int find(int x) {if(x==f[x]) return f[x]; //return x;也可行，因为x=f[x]return find(f[x]); //递归。}

3.2.并查集的合并

对于并查集的合并，只需将子节点的$f[x]$设为父节点的$f[x]$。

合并前(B->D)：

void join(int a,int b) {int fa = find(a),fb = find(b);if(fa!=fb) {f[fb]=fa; //将a的父节点设为a,b共同根节点。}}

合并后：

4.路径压缩优化

如上图所示，在节点数极高时，$C-D,B-D$这一段路径会被经过很多遍，导致效率较低，对此，可以对$find()$函数进行路径压缩优化，让其他点直接指向根节点。

int find(int x) {if(x==f[x]) return f[x]; return f[x] = find(f[x]); //在每次完成递归时对此点记录其f[x],此时f[x]一定为x点当前最新父节点} 

5.启发式合并/按秩合并

对于每次合并，让find(a)做为根节点或find(b)作为根节点均可实现并查集，但部分情况下，错误的合并会增加查找量，使效率变低。对于这些情况，需要使用启发式合并。

启发式合并核心在于将较小的合集合并到较大的里面，由于是较小的集合根节点指向较大的，两根节点合并时所产生的新路径会最小。

int siz[N];void join(int a,int b) {int fa = find(a),fb = find(b);if(fa!=fb) {if(siz[fa]<siz[fb]) swap(fa,fb); // 此时，siz[fa]一定大于siz[fb]; f[fb]=fa; siz[fa]+=siz[fb]; //将fb所在集合的大小合并至fa所在集合}}

三.例题

P3367 【模板】并查集

题目背景

本题数据范围已经更新到 1 ≤ N ≤ 2 × 10 5 1\\le N\\le 2\\times 10^5 1≤N≤2×105， 1 ≤ M ≤ 10 6 1\\le M\\le 10^6 1≤M≤106。

题目描述

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

输入格式

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

接下来 $M$ 行，每行包含三个整数 Z i , X i , Y i Z_i,X_i,Y_i Zi​,Xi​,Yi​ 。

当 Z i =1 Z_i=1 Zi​=1 时，将 X i X_i Xi​ 与 Y i Y_i Yi​ 所在的集合合并。

当 Z i =2 Z_i=2 Zi​=2 时，输出 X i X_i Xi​ 与 Y i Y_i Yi​ 是否在同一集合内，是的输出
Y ；否则输出 N 。

输出格式

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

输入输出样例 #1

输入 #1

4 72 1 21 1 22 1 21 3 42 1 41 2 32 1 4

输出 #1

NYNY

说明/提示

对于 $15\%$ 的数据，$N\le 10$，$M\le 20$。

对于 $35\%$ 的数据，$N\le 100$， M≤ 10 3 M \\le 10^3 M≤103。

对于 $50\%$ 的数据， 1≤N≤ 10 4 1\\le N \\le 10^4 1≤N≤104， 1≤M≤2× 10 5 1\\le M \\le 2\\times 10^5 1≤M≤2×105。

对于 $100\%$ 的数据， 1≤N≤2× 10 5 1\\le N\\le 2\\times 10^5 1≤N≤2×105， 1≤M≤ 10 6 1\\le M\\le 10^6 1≤M≤106， 1≤ X i , Y i ≤N 1 \\le X_i, Y_i \\le N 1≤Xi​,Yi​≤N， Z i ∈{1,2} Z_i \\in \\{ 1, 2 \\} Zi​∈{1,2}。

分析：本题为并查集模板题，无特殊点。

AC_Code:

#include \"bits/stdc++.h\"using namespace std;const int N = 1e6+5;int m,n;int f[N];int find(int x) { if(x==f[x]) return f[x]; return f[x] = find(f[x]);}void join (int a,int b) { //a为父，b为子 int fa=find(a),fb=find(b); if(fa!=fb) f[fb]=fa;}int main() { cin>>n>>m; for(int i=1;i<=n;i++) f[i]=i; //并查集初始化 for(int i=1;i<=m;i++) { int z,x,y; cin>>z>>x>>y; if(z==1) join(x,y); else if(z==2) cout<<((find(x)==find(y))?\"Y\":\"N\")<<endl; } return 0;}