并查集
并查集是一种松散的数据结构，在求连通问题时很好用．
题目：P3367 【模板】并查集
思路
首先，我们假定每一个集合都有一个节点作为代表，我们称那个节点是集合内其余节点的为领导节点．
我们定义一个数组 ，其中， 表示的意义为：若 ，即节点 是一个领导节点，则 表示节点 的领导节点．若 ，则节点 的领导节点就是节点 的领导节点．
我们可以使用递归来求一个节点 的领导节点，在求的同时，我们可以将求到的值保存到 中，下次只需要使用 的复杂度就可以求解了，这个行为叫做路径压缩．
// 查找节点i的领导节点，并进行路径压缩int find(int t){ if (f[t] != t) f[t] = find(f[t]); return f[t];}我们很容易就可以想到，对于两个节点 和 ，如果想要合并，则可以让 设定为 的领导节点．如果想要判断是否在同一集合中，只需要判断节点 和 的领导节点是否相同即可．
// 查询两个节点是否属于同一节点bool query(int a, int b){ // 查询两个节点的领导节点是否一致 return find(a) == find(b);}// 合并两个节点void merge(int a, int b){ int x = find(a), y = find(b); if (x != y) f[x] = y;}最后，千万不要忘了初始化，在最开始，所有节点的领导节点都是它自己．
// 初始化，一开始所有节点的领导节点都是它自己void init(){ for (int i = 1; i <= n; i++) f[i] = i;}复杂度分析
首先，find 函数的复杂度看似好像是最坏 的，但是由于有了路径压缩，每一次的 find 都会大大减少下一次 find 相同节点的时间，最终无限趋近于 ，但常常带有较大的常数．
因此，查询和合并的复杂度也是 ，综合一下， 次操作的总复杂度约为 ．
标程
#include <bits/stdc++.h>using namespace std;const int N = 2e5 + 6;int n, m;
// 定义一个并查集class DSU{private: // f[i]表示第i个节点的领导节点 int f[N]; // 查找节点i的领导节点，并进行路径压缩 int find(int t) { if (f[t] != t) f[t] = find(f[t]); return f[t]; }
public: DSU() { this->init(); } // 初始化，一开始所有节点的领导节点都是它自己 void init() { for (int i = 1; i <= n; i++) f[i] = i; } // 查询两个节点是否属于同一节点 bool query(int a, int b) { // 查询两个节点的领导节点是否一致 return find(a) == find(b); } // 合并两个节点 void merge(int a, int b) { int x = find(a), y = find(b); if (x != y) f[x] = y; }} dsu;
int main(){ cin >> n >> m; dsu.init(); for (int i = 1; i <= m; i++) { int z, x, y; cin >> z >> x >> y; if (z == 1) { dsu.merge(x, y); } else { cout << (dsu.query(x, y) ? "Y" : "N") << endl; } } return 0;}带权并查集
题目：P2024 食物链
题目描述
动物王国中有三类动物 ，这三类动物的食物链构成了有趣的环形． 吃 ， 吃 ， 吃 ．
现有 个动物，以 编号．每个动物都是 中的一种，但是我们并不知道它到底是哪一种．
有人用两种说法对这 个动物所构成的食物链关系进行描述：
- 第一种说法是
1 X Y，表示 和 是同类． - 第二种说法是
2 X Y，表示 吃 ．
此人对 个动物，用上述两种说法，一句接一句地说出 句话，这 句话有的是真的，有的是假的．当一句话满足下列三条之一时，这句话就是假话，否则就是真话．
- 当前的话与前面的某些真的话冲突，就是假话；
- 当前的话中 或 比 大，就是假话；
- 当前的话表示 吃 ，就是假话．
你的任务是根据给定的 和 句话，输出假话的总数．
输入格式
第一行两个整数，，表示有 个动物， 句话．
第二行开始每行一句话．格式见题目描述与样例．
输出格式
一行，一个整数，表示假话的总数．
说明/提示
对于全部数据，，．
．
考虑对于每一个加入并查集的元素，尝试对于每一个元素都维护一个权值 ，权值为 0 的吃权值为 1 的，1 吃 2，2 吃 0．权值大于 2 则模 3 处理．
定义 表示节点 与节点 的权值之差．
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！