并查集

并查集简述

---

并查集

——并查集是一种树形结构，简单来说就是让有关系的单元之间用一个代表元来表示相当于把有关系的单元放在同一个集合。

---

并查集三种操作 ——首先对每个单元自定义一个代表元fa，让这个fa == 单元本身。 -查–查单元的代表元fa。 -并–将有联系的单元的代表元fa并在一起，最终让同属与一个集合的单元的代表元都相同。

---

#include <cstdio> #include <iostream> #include <algorithm> using namespace std; const int MAxn = 1e5 + 5; int fa[MAxn]; // 存第I个的代表元 void Find(int x) // 查操作，通过递归查找x的代表元； { if(fa[x] == x) return x; return fa[x] = find(fa[x]); //查当前点的代表元； } int main() { int n; cin >>　ｎ； for(int i = 1; i <= n; i++) fa[i] = i; //并查集第一步操作,初始化第I个的代表元 int u, v; cin >> u >> ｖ； f[find(u)] = find(v); //并操作，每次修改的是u的代表元,让u,和v的代表元相同； return 0; }

并查集的代码比较简短， 初学的时候还是需要多多领悟，才会懂。当要查询一个点和另一个点是否同属于一棵树，或者有无关系的时候，并查集比dfs或者bfs搜索算法的时间复杂度降低很多，当数据变得很大的时候，并查集能快速判断两个点之间是否有联系。