1.合并集合
一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。
现在要进行 m 个操作，操作共有两种：
M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；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; else cout << "No" << endl; } } return 0; }
2. 连通块中点的数量
给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。
现在要进行 m 个操作，操作共有三种：
C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；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; else cout << "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 句话有的是真的，有的是假的。
当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
- 当前的话与前面的某些真的话冲突，就是假话；
- 当前的话中 X 或 Y 比 N 大，就是假话；
- 当前的话表示 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; }
