14.1 Dynamic Connectivity and the Disjoint Sets Problem
本节讲的是 “union-find” 算法，中文翻译就很熟悉了：并查集
14.1.1 The Disjoint Sets Data Structure
上来那开宗明义，啥是并查集啊！
The Disjoint Sets data structure has two operations:
- connect(x, y): Connects x and y.
- isConnected(x, y): Returns true if x and y are connected. Connections can be transitive, i.e. they don’t need to be direct.
并查集只有两个操作：
- 合并/连接
- 查询
public interface DisjointSets {
void connect(int p, int q);
boolean isConnected(int p, int q);
}14.1.2 The Naive Approach
这个其实没意思，就是这个 API 它用了会是啥效果
14.2 Quick Find
如何实现呢：
若尝试 Map ， Slow because you have to iterate to find which set something belongs to.
这里其实的意思是，我们选择的底层的实现方式是会影响效率的，国内的挨过数据结构毒打的同学就悟了：这就是所谓的逻辑结构和物理结构嘛，不同物理结构是实现会导致不同的操作呗
14.2.1 SETS
Idea #1: List of sets of integers, e.g. [{0, 1, 2, 4}, {3, 5}, {6}] ： List>.
初始化 ： [{0}, {1}, {2}, {3}, {4}, {5}, {6}]
若是要查找 ：Requires iterating through all the sets to find anything. Θ(N).
Important point: By deciding to use a List of Sets, we have doomed ourselves to complexity and bad performance.
用错了实现数据结构，导致了这样的情况
14.2.1 LIST
Idea #2: list of integers where ith entry gives set number (a.k.a. “id”) of item i.
这个的意思是：将 int[x] 指向其根节点
package lec14_Disjiont_Sets;
public class QuickFindDS implements DisjointSets {
private int[] id;
@Override
public boolean isConnected(int p, int q) {
return id[p] == id[q];
}
@Override
public void connect(int p, int q) {
int pid = id[p];
int qid = id[q];
for (int i = 0; i < id.length; i++) {
if (id[i] == pid) {
id[i] = qid;
}
}
}
// 初始化，所有的元素都是独立的
public QuickFindDS(int N) {
id = new int[N];
for (int i = 0; i < id.length; i++) {
id[i] = i;
}
}
}这里需要强调的是：
虽然 isConnected 是极快的，但是 connect 是很慢的，为什么，那每次遍历都往祖坟上刨肯定慢啊
14.3 Quick Union
为了解决 connect 的速度问题，我们要进行一个改进
跳过那些巴拉巴拉的东西，让 int[x]指向其父节点而不是root,而root节点值为 -1
package lec14_Disjiont_Sets;
public class QuickUnionDS implements DisjointSets {
private int[] parent;
public QuickUnionDS(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
private int find(int p ){
int r = p;
while (parent[r] >=0 )
{ r = parent[r]; }
return r;
}
@Override
public void connect(int p, int q) {
int i = find(p);
int j = find(q);
parent[i] = j;
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
}
14.4 Weighted Quick Union
略，其实是油管的翻译有问题了，而且这玩意我考研不考
14.5 Path Compression (CS170 Preview)
略
ACWING
并查集：
- 将两个集合合并
- 询问两个元素是否在一个集合当中
暴力存储：
尝试数组存储 ：belong[x] = a (x的集合)
if(belong[x] == belong[y]) O(1)
但是合并那是及其耗时的，怎么办呢：
基本原理：
用树的形式维护所有集合，每一个集合用一棵树维护，其编号为根节点的编号，对每一个点都存储其父节点p[x]
- 如何判断树根： if[p[x] == x]
- 如何求 x 的集合编号 ：while（p[x]≠x） x = p[x]; //这里会导致高时间复杂度
- 如何合并两个集合：一个根做另一个根的子节点 p[x] = y
对 2. 的优化，每次找到之后，将路径上的所有点都指向根节点（所谓的路径压缩）
还有一个优化：按秩合并？还有 路径减半 路径分裂吗，但是关我屁事，会用路径压缩写就完事了
836. 合并集合
一共有 nn 个数，编号是 1∼n1∼n，最开始每个数各自在一个集合中。
现在要进行 mm 个操作，操作共有两种：
M a b，将编号为 和 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作； a a b bQ a b，询问编号为 和 的两个数是否在同一个集合中； a a b b
输入格式
第一行输入整数 nn 和 mm。
接下来 mm 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。
输出格式
对于每个询问指令 Q a b，都要输出一个结果，如果 aa 和 bb 在同一集合内，则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1≤n,m≤1051≤n,m≤105
输入样例：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4输出样例：
Yes
No
Yes#include "iostream"
using namespace std;
const int N = 100010;
int p[N];
int n,m;
int find(int x) // return x的root + 路径压缩
{
if(p[x]!= x) p[x] = find(p[x]);
return p[x];
// return p[x] == x ? x : p[x] = find(p[x]);
}
int main()
{
cin>>n>>m;
for (int i = 1; i <= n; i ++ ) p[i] = i;
while (m -- ){
// char op[2];
char c;
int a,b;
// cin >>op>>a>>b;
cin >>c>>a>>b;
// if(op[0] == 'M') p[find(a)] = find(b);
if(c == 'M') p[find(a)] = find(b);
else {
if (find(a) == find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}