c++算法学习笔记 (14) 并查集

1.合并集合

一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。

现在要进行 m 个操作，操作共有两种：

1. M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
2. Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；

输入格式

第一行输入整数 n 和 m。

接下来 m 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。

输出格式

对于每个询问指令 Q a b，都要输出一个结果，如果 a 和 b 在同一集合内，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1≤n,m≤10^5

输入样例：

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例：

Yes
No
Yes

#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int p[N];       // 存父节点
int find(int x) // 最重要！！！！！！！！
{               // 返回x所在集合的编号（x的根编号）+路径压缩if (p[x] != x)p[x] = find(p[x]);return p[x];
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){p[i] = i;}while (m--){char op;int a, b;cin >> op >> a >> b;if (op == 'M'){                         // 合并p[find(a)] = find(b); // a祖宗父亲为b祖宗}if (op == 'Q'){ // 询问编号为a和b的两个数是否在同一个集合中if (find(a) == find(b))cout << "Yes" << endl;elsecout << "No" << endl;}}return 0;
}

2. 连通块中点的数量

给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。

现在要进行 m 个操作，操作共有三种：

1. C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
2. Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
3. Q2 a，询问点 a 所在连通块中点的数量；

输入格式

第一行输入整数 n 和 m。

接下来 m 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

输出格式

对于每个询问指令 Q1 a b，如果 a 和 b 在同一个连通块中，则输出 Yes，否则输出 No。

对于每个询问指令 Q2 a，输出一个整数表示点 a 所在连通块中点的数量

每个结果占一行。

数据范围

1≤n,m≤105

输入样例：

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

输出样例：

Yes
2
3

#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int p[N], size1[N]; // size:每个集合点的数量（只有根节点的size有意义）
int find(int x)
{if (p[x] != x){p[x] = find(p[x]);}return p[x];
}int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){p[i] = i;size1[i] = 1;}while (m--){string op;int a, b;cin >> op;if (op == "C"){cin >> a >> b;// 特判if (find(a) == find(b))continue;// 注意下面两条代码的顺序size1[find(b)] += size1[find(a)];p[find(a)] = find(b); // 注意！！！！！！！}if (op == "Q1"){cin >> a >> b;if (find(a) == find(b))cout << "Yes" << endl;elsecout << "No" << endl;}if (op == "Q2"){cin >> a;cout << size1[find(a)] << endl;}}return 0;
}

 3.食物链​​​​​​​

动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。

A 吃 B，B 吃 C，C 吃 A。

现有 N 个动物，以 1∼N 编号。

每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 N 个动物所构成的食物链关系进行描述：

第一种说法是 1 X Y，表示 X 和 Y 是同类。

第二种说法是 2 X Y，表示 X 吃 Y。

此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。

当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1. 当前的话与前面的某些真的话冲突，就是假话；
2. 当前的话中 X 或 Y 比 N 大，就是假话；
3. 当前的话表示 X 吃 X，就是假话。

你的任务是根据给定的 N 和 K 句话，输出假话的总数。

输入格式

第一行是两个整数 N 和 K，以一个空格分隔。

以下 K 行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中 D 表示说法的种类。

若 D=1，则表示 X 和 Y 是同类。

若 D=2，则表示 X 吃 Y。

输出格式

只有一个整数，表示假话的数目。

数据范围

1≤N≤50000,
0≤K≤100000

输入样例：

100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

输出样例：

3

 

#include <iostream>
using namespace std;
const int N = 50005;
int n, k; // 并查集：可以维护额外信息
// 重点：用与根节点的距离表示与根节点的关系
// 距离=0：根节点
// 距离=1：吃根节点
// 距离=2：2吃1，1吃根，所以此点被根吃
// 距离=3：与根节点是同类
// 距离每3一循环（余1：吃根节点；余2：被根节点吃；余0：与根节点是同类）
// x吃y:y->x的距离是1（距离为i：第i代）
int p[N], d[N];
int find(int x)    // 路径压缩时将与父节点的距离更新成与根节点的距离
{                  // 维护d数组if (p[x] != x) // x不是树根{int t = find(p[x]); // t记录根节点d[x] += d[p[x]];    // 自己到根(x到p[x]的距离+p[x]到根节点的距离)p[x] = t;}return p[x];
}
int main()
{cin >> n >> k;for (int i = 1; i <= n; i++){p[i] = i;d[i] = 0;}int ans = 0;while (k--){int t, x, y;cin >> t >> x >> y;if (x > n || y > n)ans++;else{int px = find(x), py = find(y);if (t == 1){                                      // X和Y是同类if (px == py && (d[x] - d[y]) % 3) // xy在同一棵树中且余数不同{ans++;}else if (px != py){               // 不在一棵树中p[px] = py; // x的根指向y的根// 计算两根之间应该赋什么距离：(d[x]+?-d[y])%3==0  ?=d[y]-d[x]  这里为了满足xy是同类d[px] = d[y] - d[x];}}else if (t == 2) // X 吃 Y,则(d[x]-d[y])%3=1 or (d[y]-d[x])%3=2{if (px == py && (d[x] - d[y] - 1) % 3){ans++;}else if (px != py){ // 不在一棵树中p[px] = py;d[px] = d[y] + 1 - d[x];}}}}cout << ans;return 0;
}