并查集初识 如果给你一些顶点，并且告诉你每个顶点的连接关系，你如何才能快速的找出两个顶点是否具有连通性呢？如「图 5. 连通性问题」，该图给出了顶点与顶点之间的连接关系，那么，我们如何让计算机快速定位 (0, 3) , (1, 5), (7, 8) 是否相连呢？此时我们就需要机智的「并查集」数据结构了。很多地方也会称「并查集」为算法，这也没问题。连通性问题「并查集」的主要作用是用来解决网络中的连通性。这里的「网络」可以是计算机的网络，也可以是人际关系的网络等等。例如，你可以通过「并查集」来判定两个人是否来自同一个祖先。「并查集」常用术语父节点：顶点的直接父亲节点。如「图5. 连通性问题」中，顶点 3 的父节点是 1；顶点 2 的父节点是 0；顶点 9 的父节点是自己本身 9。根节点：没有父节点的节点，本身可以视为自己的父节点。如「图5. 连通性问题」中，顶点 3 和 2 的根节点都是 0；0 即是自己本身的父节点，也是自己的根节点；顶点 9 的根节点是自己本身 9。「并查集」基本思想 视频内容摘要：如何在计算机中设计出「并查集」数据结构「并查集」的 find 函数；「并查集」的 union 函数。 视频链接「并查集」的两个实现方式Quick Find 实现方式：它指的是实现「并查集」时，find 函数时间复杂度很低为 O(1)O(1)，但对应的 union 函数就需要承担更多的责任，它的时间复杂度为 O(N)O(N)。Quick Union 实现方式：它指的是实现「并查集」时，相对于 Quick Find 的实现方式，我们通过降低 union 函数的职责来提高它的效率，但同时，我们也增加了 find 函数的职责。Quick Find 方式实现并查集Quick Find工作原理： 视频链接代码实现与验证#include <bits/stdc++.h> using namespace std; class UnionFind{ private: int* root; int length; public: UnionFind(int size):length(size){ root = new int[size]; for(int i=0;i<length;i++){ root[i] = i; } } int find(int x){ return root[x]; } void merge(int x,int y){ int rootX = find(x); int rootY = find(y); if(rootX!=rootY){ for(int i=0;i<length;i++){ if(root[i]==rootY) root[i] = rootX; } } } bool isconnected(int x,int y){ return find(x)==find(y); } }; int main(){ UnionFind a(10); a.merge(1,2); a.merge(2,5); a.merge(5,6); a.merge(6,7); a.merge(3,8); a.merge(8,9); cout<<a.isconnected(1,5)<<' '<<a.isconnected(5,7)<<' '; cout<<a.isconnected(4,9)<<' '; a.merge(9,4); cout<<a.isconnected(4,9); } 时间复杂度 | | UnionFind 构造函数 | find 函数 | merge函数 | isconnected 函数 | | -------------- | ------------------ | --------- | --------- | ---------------- | | 时间复杂度 | O(N) | O(1) | O(N) | O(1) | 注：N 为「图」中顶点的个数。Quick Union 方式实现并查集Quick Union的工作原理 视频链接为什么 Quick Union 比 Quick Find 更加高效？ 总体来说，Quick Union 是比 Quick Find 更加高效的。为什么呢？ 视频链接代码实现与验证#include <bits/stdc++.h> using namespace std; class UnionFind{ private: int* root; int length; public: UnionFind(int size):length(size){ root = new int[size]; for(int i=0;i<length;i++){ root[i] = i; } } int find(i…