本讲定位：图论系列第九讲。并查集是本系列代码量最小的一讲——核心三行——但它是第 10 讲 Kruskal 的地基，所以排在最小生成树之前。它只回答一个问题：这两个点连通吗；但配上”扩展域”“带权”“离线逆序”三个变形之后，它能回答”这两个人是不是敌人”“这两句话矛不矛盾”“删掉这些点还剩几块”。本讲做了六组实测，四个数字值得先记住：不加任何优化的并查集在 $n=10^5$ 的恶意数据上跑 24.49 s，加一行路径压缩后 0.0005 s（快约 4.9 万倍）；
fa[x] = y这个写法实测错 29.0%，而且其中 16.25% 是直接死循环而不是答案错；只按大小合并时树高实测恰好等于 $\log_2 n$（$n=2^{20}$ 时是 20，一层不差）；递归版find在 8 MB 栈下约 69 万层倒下。文中所有代码经g++ -O2 -std=c++14 -Wall编译运行，P3367、P1525、P1196、P2024 与洛谷官方样例核对通过。前置知识：第 01 讲（图的存储、连通块的概念）、第 02 讲（一遍 DFS 数连通块，以及递归爆栈那一节——本讲会再遇到一次）。第 5.3 节会提到二分图判定，但不需要提前学第 15 讲。不需要任何最短路知识，第 05～08 讲没跟上的同学可以直接学本讲。
适合对象：第 2、3、4 节标 J（CSP-J 复赛必会，且必须能默写）；第 5 节标 J⭐ / S；第 6、7 节标 S；第 8 节标 S⭐。
第 02 讲讲过：一遍 DFS/BFS 就能数出连通块个数，$O(n+m)$，很便宜。
现在把问题改一个字——边是一条一条加进来的：
初始 $n$ 个点、没有边。接下来 $m$ 次操作，每次要么”在 $x$ 和 $y$ 之间加一条边”，要么”问 $x$ 和 $y$ 现在是否连通”。
朴素办法一：每次询问重跑一遍 DFS。 单次 $O(n+m)$，总共 $O(m(n+m))$。$n,m$ 到 $10^5$ 就是 $10^{10}$，没有希望。
朴素办法二：染色数组。 开 col[i] 表示 $i$ 属于哪个连通块，询问就是 $O(1)$ 的 col[x] == col[y]。但合并要把一整块的颜色全刷成另一个颜色，单次最坏 $O(n)$，总共 $O(nm)$。还是不行。
卡点很清楚：办法一查询快不了，办法二合并快不了。我们要的是两个都快。
顺带说清一件事：这类”边动态加入”的问题，DFS 从原理上就不合适。DFS 的 $O(n+m)$ 是”从零把整张图走一遍”的代价，它没有任何增量能力——加一条边，前一次的成果全部作废。而并查集从一开始就是为增量设计的。
思路只有一句话：
每个连通块用一棵树表示，树根当这个块的”代表”。判连通 = 比较两个点的根。
于是只需要一个数组 fa[x]（$x$ 的父亲，根的父亲是自己）和三个操作：
int fa[N];
void init(int n) { for (int i = 1; i <= n; i++) fa[i] = i; } // 每个点自成一块
int find(int x) { return fa[x] == x ? x : find(fa[x]); } // 一路向上找根
void unite(int x, int y) { fa[find(x)] = find(y); } // 把一个根挂到另一个根下
bool same(int x, int y) { return find(x) == find(y); }
unite 那一行是全篇最重要的一行，第 3 节会用实测告诉你写错它的代价。