所有代码详见：https://github.com/jingminglake/Leetcode

总体思路

• 并查集是什么

图的信息就是点集合 + 边集合。

并查集在一开始就是表示点集合，但是这些点是一群孤立的点，之后就是通过union操作+边集合信息，把点连接起来，在这种连接的过程中， 可以使用find操作来知道当前的两个点之间是否是连通的。

• 并查集的具体实现

并查集使用一个hashmap来装所有结点，以及该结点对应的总领导（key是结点，value是结点对应的总领导）。这张表叫parent、father表或者boss表。

一开始全是孤立点的时候，每个结点的总领导就是自己。根据边进行点连接的时候，就相当于两家公司进行合并，此时任意选其中一个公司的总领导作为合并后的总领导。 具体过程就是：先使用find操作找到两个结点的总领导ceo1，ceo2，然后把一个总领导（例如ceo1）的总领导变为ceo2。如果find(A) == find(B)，那么说明A和B在本来就是同一家公司工作。

find操作，可以找到一个结点的总领导（CEO）结点，而并不关心中间领导。由于信息是实时更新的，因此parent[x]并不一定就是x的总领导，而是要检查parent[x]是不是还存在领导。而如果parent[x] == x的时候，也就是CEO的领导是自己的时候，那就是遇到终止条件。

所以常规解法是一步步向上去找，最坏情况下树退化成一条链，消耗时间O(N)，代码如下：

int find(int x) {
    if (parent[x] == x) return x;
    return find(parent[x]);
}

优化一：路径压缩。在找总领导的过程中，可以实时更新所有查询路径上的点的总领导，也就是把这条链上的点全部直接挂到CEO下面：

int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);   // 回溯时顺手改挂
}

优化二：按大小合并（union by size）。只有路径压缩是不够的（原因见下面的复杂度），因为合并时如果无脑把一个根挂到另一个根上，完全不看谁大谁小，树还是可能长得很高。正确做法是让小集合挂到大集合下面：

void unite(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return;                    // 本来就是同一家公司
    if (size[ra] > size[rb]) swap(ra, rb);   // 保证小的挂到大的下面
    parent[ra] = rb;
    size[rb] += size[ra];
    count--;                                 // 只在真的发生合并时才减
}

另一种等价写法是按秩合并（union by rank）：秩是这棵树高度的一个上界，合并时矮树挂到高树下面。注意秩不等于真实高度——路径压缩会让实际高度变矮，但我们并不去更新秩（要精确维护高度，每次压缩都得回溯修正，代价太大），所以秩只增不减，作为上界它仍然是合法的合并依据。这就是它叫rank而不叫height的原因。两种写法效果等价，但按大小更划算，因为size数组本身还有别的用处（见下面技巧3）。

所以，并查集的完整模板是：

class UnionFind {
    vector<int> parent, size;
    int count;                     // 当前连通分量个数
public:
    UnionFind(int n) : parent(n), size(n, 1), count(n) {
        for (int i = 0; i < n; i++) parent[i] = i;   // 初始化为自己
    }

    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    void unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return;
        if (size[ra] > size[rb]) swap(ra, rb);
        parent[ra] = rb;
        size[rb] += size[ra];
        count--;
    }

    bool connected(int a, int b) { return find(a) == find(b); }
    int getCount() { return count; }
};

两个容易写错的地方：

（1）parent必须初始化为自己（parent[i] = i），不能初始化为-1或者0。因为find的终止条件就是parent[x] == x，初值对不上会直接越界。

（2）union是C++的关键字，不能拿来做函数名（Java里则是合法的），要改叫unite或者merge。

• 复杂度

这里最容易记错。首先，find和unite的复杂度永远相同，因为unite内部必须先调用两次find，那两次find才是大头，最后的指针赋值才是O(1)。所以说”unite是O(1)”等价于说”find是O(1)”，是同一个错误。

注意只有路径压缩是达不到常数的。路径压缩只在恰好被查过的那条路径上生效，如果合并时无脑挂导致树很高，总能挑出还没被压缩过的深链来查，摊还下来是O(logN)。

α(N)是阿克曼函数的反函数，增长极其缓慢，对所有现实中可能出现的N（哪怕N = 2^65536）都有α(N) ≤ 5，所以工程上可以当常数用，但写复杂度分析的时候要写O(α(N))，不能写O(1)。

• 并查集使用情况

真正不可替代的信号是动态连通性：边是一条一条来的，而且只增不减，每来一条就要立刻回答”这两个点连上了吗”。如果所有边一开始就给全了，DFS/BFS一遍扫完也能做，未必要用并查集；一旦变成边流式到达、每加一条就要查一次，DFS每次都得重扫O(V+E)，并查集才是O(α(N))。684和261都是这个形态。

关于点的合并或者点的连边，关于集合的合并、查询，一般用并查集。但注意并查集不提供删边操作。

• 不能删边，反过来给了一个通法：时间倒流

为什么天然做不到删边：parent数组只记录”我挂在谁身上”，不记录”我为什么挂上去”。合并是有损的、不可逆的，尤其路径压缩之后原来的树形结构被拍扁，中间的父子关系整个丢了，没有任何信息可以还原到合并之前。集合只能合、不能拆。

由这条限制直接推出一个套路：

凡是题目在做”删边／删点／拆分”，就把时间倒过来，变成”加边／加点／合并”。

803题（Bricks Falling When Hit）就是这么做的：反着来添加被打掉的坐标，每次当作添加砖。同类的还有离线删边连通性查询、逐位变0的题目，都是倒序处理。

• 并查集其他技巧：

（1）求连通区域的个数。并查集可以加一个变量来表示公司的个数（连通区域的个数）。初始时候该变量为元素个数，每次unite操作时候，只要两个点不属于一个公司时候，将变量减1。注意不是每次调用unite都减，只有两个根确实不同、真的发生了合并才减。

也可以在建立连通图后计算：通过遍历每一个节点x，看其parent[x]是否等于自己，如果相等，算作一个区域数。 同理，想要知道每片连通区域的具体结点信息，可以遍历parent数组，将区域的parent结点作为key，将子节点存入指向的vector。所以”列出某个连通分量的所有成员”是支持的，只是需要O(N)扫一遍，而不是O(1)。

（2）知道某些点之间互相连通的时候，可以O(n)时间建立连通，原理就是把其他所有点连接到第一个点上，那么自然所有点就连通了。注意是每个点各跟第一个点连一次，一共n-1次unite，不是两两相连（那是O(n^2)）。

（3）并查集可以加一个size数组来记录以key为总领导的公司的员工数量。size数组只有在该key确实是CEO时候去查才有意义，否则没意义。上面的模板里，size已经同时兼任了合并优化的依据。

具体题目

261. Graph Valid Tree

题意：验证图是不是树，给出的是结点以及结点直接连接的信息。给出的图信息是点，加边信息。

解：树的概念：树是连通且不存在回路（环）的图，也意味树有一个性质，就是边的数量等于顶点数量减1。

所以验证图是不是树要满足两个条件，一个是图上的任意两点之间连通，第二是图不存在环。判断无向图是否有环，只需要建立标记数组，只要访问回原来结点，那么就有环。

还有一个可以不检测有环的方法：只需要判断边的数量是不是顶点数量减1就可以。这样只需满足这一条件，再加上图是连通的，就满足图是树了。

方法一：dfs。首先再次说一下，dfs本质就是树结构的回溯，对于图，也就是选择一个作root。 对于无向图，存在环的判断就是：遍历时候一旦遇到已经经过dfs处理访问过的结点，那么就存在环。但是其中有一个特例，因为两个结点互为邻居，所以加入邻居结点的时候，由于父节点一定是已经访问过，所以常规dfs情况下，只需要去掉访问过的结点就行了，但是判断环的dfs中我们不能知道一个vistited结点是因为有环所以造成找到visited结点还是因为天生的找到父节点的情况，所以我们改变进入下一层的条件：明确的指出，排除掉邻居是父节点的情况。

方法二：bfs。分为三种状态，正在访问状态，未访问状态，和访问结束状态。bfs的时候，如果邻居结点都被压栈，那么状态为已访问。结点进入队列后标记为正在访问状态。结点处理邻居结点的时候，如果邻居结点处于正在访问状态，那么返回false；如果是已访问状态，那么不用压栈。

方法三：并查集。对于一个pair，看两个连接的点在已构建出的图中是否属于同一个公司，如果属于同一个公司，那么说明他们除了相互连接外，还有其他路径连通，所以就是存在环。

另外：判断是否连通，就看边的数量是不是顶点减1，如果是，那么说明是连通的。

此题还可以把方法一、二进行优化，比如一开始就看边和点的关系是不是满足tree，不满足直接返回false，如果满足，那么不可能存在环，问题就简化为判断图是否是连通的。

721. Accounts Merge

题意：找到所有人和其对应的邮箱的列表，人名不是id，邮箱才是id。

解：此题是图的问题，如果不转化为图（也就是不转化为合适的数据结构），而只是扫描的话，就会发现很难将当前处理的结果存入之前的结果。

所以还是利用合适的数据结构来解题会比较舒适。首先，将email作为id建立关系图，处于同一账户元素里面的email是互相连通的，但是谁作为第一邻居，其实是无所谓的，简单起见，把第一个email和剩余email相连，这样所有email之间都连通了。这样扫描一遍所有账户后，就得到了email的邻接表表示的图。

另外，第一遍扫描所有账户的时候，新建hash表，建立email指向用户名的映射，这样方便找到email对应的用户名。另外，取用户名也可以放在下一次扫描所有账户的时候。

方法一：使用并查集。第一遍扫描所有账户将连通的email连通，第二遍扫描并查集hashmap时候把每个结点的所在的CEO的name取出作为key，形成map，最后再把map转成vector即可。

方法二：dfs。第一遍扫描所有账户将连通的email连通（每个账户其余email均与第一个email相连），然后，进行dfs，使用visited数组来记录结点是否访问，dfs起点是每个账户第一个email。

684. Redundant Connection

题意：检测图是不是树，给出的图多出了一条边，因此形成了环，此题给出的边的链接是小节点连接到大节点。求多余的那条边，如果有多种选项，那么最后一个多余的pair做答案。

解：此题使用并查集做，也就是说并查集也可以检测图中是否有环。对于给出的边，尝试链接到原来的图上面，先检查当前两个点在原图中是不是属于一个结点，如果是，说明两个点在未加入前已经是连通的，因此如果再加入那么必定会形成环，也就是多余的边。

如果使用dfs，那么先建图，然后检测环是不行的，因为找不到最后一个pair。一个改进的方法就是，一次加一条边到图上，然后在之前检测当前加入的边的两个顶点是不是已经连通了，已经连通的话就是答案，思路和unionfind一致。

685. Redundant Connection II

题意：与684的区别是，此题是有向图，而且有向图表面的那种环也算环。

解：此题比较难想到通用解题思路。所以从给出的例子里面找规律，看能不能总结出要求删除的边的特点。特点就是：（1）如果一个结点存在两个入度，那么两个入度中的一个必作为答案。其中具体哪个作为答案分两种情况：一种是如果去掉其中一个，剩下的图形成不了环（使用类似无向图的unionfind检测，一边加，一边检测），那么说明删除的是答案；第二种情况是，如果去掉其中一个，剩下的还是存在环，那么另一个是答案。（2）如果所有节点都是一个入度，但是存在环，此时使用类似无向图的unionfind检测解题就可以。

128. Longest Consecutive Sequence

题意：找出数组的最长大小连续(consecutive)的序列的长度，例如[100, 4, 200, 1, 3, 2]的最长大小连续的序列是[1, 2, 3, 4]，长度是4。

解：此题思想是union find，扫描数组，当我们扫描到1的时候，那么我们会先看他的邻居结点0和2是否已经在之前被扫描过，如果扫描过，那么把自己链接到原来的那一片连通的区域中，也就是说，原来一片区域的总结点数要加1。实际上，这片区域就是一个区间，我们可以使用一个技巧，也就是只使用区间左右端点来记录区间的大小，因为如果扫描的一个点落在了区间以内，那么这个点并不会使得区间的大小（也就是连续序列的长度）变化，而只可能是点落在区间左端点之前，或者右端点之后才会使得区间大小加1。

扫描数组，使用hash表记录每个元素作为所属区间边界的长度，对于元素num，先看num有没有处理过，如果没有处理过才进行处理，也就是说处理之前先查表，如果存在了，那么就直接continue。因为存在了，说明num作为边界已经处理过了，现在是必属于某个区间里面的，所以没有必要更新了。

如果num存在，那么看num-1和num+1是否存在。

如果num-1和num+1都不存在，那么num对应长度为1，存入hash表。

如果num-1存在而num+1不存在，说明num-1所在区间可以更新1，num-1所在区间本来右边界是num-1，现在更新的区间的右边界显然是num，那么在看num-1所属区间的左边界在哪，显然，hash[num-1]就是区间大小，也就是说左端点大小是num - hash[num - 1]，其在hash表中对应的值应该加1。

同理处理num-1不存在而num+1存在的情况。

当num-1和num+1都存在的时候，要把最终长度更新到两边的边界，num标记为已访问就可以了，因为我们知道，每次其实是一个一个元素的加到hash表中的，也就是说，加入num之前，num-1和num+1所在的区间的每个元素都被访问过了。

扫描过程中记录更新中可以产生的最大值，作为结果返回。

803. Bricks Falling When Hit

题意：二维矩阵表示，0表示空，1表示砖。二维矩阵第0行看作天花板。先给出这样一个矩阵，然后在给出一个二维数组坐标，表示打掉该坐标处的砖。现在要求的是每次掉落的砖，砖会掉落如果它不与天花板连通。

解：思路一：并查集。反着来添加打掉的坐标，每次当作添加砖，然后看每次有多少新砖可以连通到天花板。

具体做法是：首先，计算出初始状态的所有点的连通性：先去掉准备打掉砖的坐标，然后把剩余的砖，进行二维数组的扫描，每次考虑当前坐标和他的左边和上边的点，如果当前点和左边的点都是砖，那么进行一次union操作。两个parent合并的时候，如果有第0行的结点，那么就选其作为parent结点。

其次，倒着加入打掉的坐标，如果四个方向上有1，那么union操作，然后看新的图有多少连通点，减去之前状态的连通点就可以知道这一步连通了多少个新点，也就是会掉多少点。 其中计算连通点有一个技巧，就是把所有的顶层的点和一个额外空间进行连接，在把连通点个数记录到额外空间对应的值，这样可以一次查出所有连通点数量。

• 上一篇
  Leetcode按题目类型总结（八）
• 下一篇
  Leetcode按题目类型总结（十）