我以前也不会呀,自从用了并查集之后,嗨,效果还真好!我们全家都用它!——某大佬
关于并查集
,有以下题型:
- LeetCode130——Surrounded Regions——给了个二维 grid,把里面O全部变成X,但是边界和边界联通区域内的O保留(也能用DFS)
- LeetCode261——Graph Valid Tree——给了N个结点和一个边的集合,问这个边的集合能不能构成一棵树
- ...
并查集
是一种树形数据结构,它由一个整型数组
和两种操作
组成:
整型数组
——记录每一个点对应前导点的下标find
——确定元素属于哪一个子集,可以使用它来确定两个元素是否属于同一个子集union
——将两个子集合并成一个集合
并查集
的通用代码(看完你就明白这是个啥玩意儿了):
class UnionFind { public: UnionFind (int sz) { pre = vector<int>(sz); for (int i = 0; i < sz; ++i) { pre[i] = i; } } // 查找根节点 int find(int x) { int root = x; while (pre[root] != root) { root = pre[root]; } // 路径压缩(降低时间复杂度) int start = x; while(pre[start] != root) { int tmp = pre[start]; pre[start] = root; start = tmp; } return root; } // 合并子集 void join(int x, int y) { int rootX = find(x), rootY = find(y); if (rootX != rootY) pre[rootY] = rootX; } private: vector<int> pre; };
图片如下:
基于上面👆并查集的框架,稍微修改一下,即可得到本题代码:
// // Created by jt on 2020/9/7. // #include <vector> #include <iostream> using namespace std; class UnionFind { public: UnionFind (int sz) { pre = vector<int>(sz+1); for (int i = 1; i < sz; ++i) { pre[i] = i; } } // 查找根节点 int find(int x) { int root = x; while (pre[root] != root) { root = pre[root]; } // 路径压缩(降低时间复杂度) int start = x; while(pre[start] != root) { int tmp = pre[start]; pre[start] = root; start = tmp; } return root; } bool isSameSet(int x, int y) { return find(x) == find(y); } // 合并子集 void join(int x, int y) { int rootX = find(x), rootY = find(y); if (rootX != rootY) pre[rootY] = rootX; } private: vector<int> pre; }; int main() { int N, M; cin >> N >> M; UnionFind uf(N); for (int i = 0; i < M; ++i) { int a, b, c; cin >> a >> b >> c; if (a == 1) { if (uf.isSameSet(b, c)) cout << "Yes" << endl; else cout << "No" << endl; } else { uf.join(b, c); } } }