本文共 1384 字，大约阅读时间需要 4 分钟。

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 $N,M$ ，表示共有 $N$ 个元素和 $M$ 个操作。 接下来 $M$ 行，每行包含三个整数 $Z_i,X_i,Y_i$ 。 当 $Z_i=1$ 时，将 $X_i$ 与 $Y_i$ 所在的集合合并。 当 $Z_i=2$ 时，输出 $X_i$ 与 $Y_i$ 是否在同一集合内，是的输出 $Y$ ；否则输出 $N$ 。

输出格式

对于每一个 $Z_i=2$ 的操作，都有一行输出，每行包含一个大写字母，为 $Y$ 或者 $N$ 。

输入输出样例

输入 #1

4 72 1 21 1 22 1 21 3 42 1 41 2 32 1 4

输出 #1

NYNY

说明/提示

对于 $30\%$ 的数据，$N\le 10，M\le 20$ 。 对于 $70\%$ 的数据，$N\le 100，M\le 10^3$ 。

对于 $100\%100$ 的数据，$1\le N\le 10^4，1\le M\le 2\times 10^5$ 。

题意：实现一个简单并查集算法。

---

思路：无。代码如下：

#include 
   
    using namespace std;const int maxn = 1e4 + 10;int father[maxn];void merge(int x, int y) {
   	if (father[x] < father[y]) {
   		father[x] += father[y];		father[y] = x;	} else {
   		father[y] += father[x];		father[x] = y;	}}int find(int x) {
   	return father[x] < 0 ? x : father[x] = find(father[x]);}int main() {
   	int n, m, z, x, y;	scanf("%d%d", &n, &m);	for (int i = 1; i <= n; ++i) father[i] = -1;	for (int i = 0; i < m; ++i) {
   		scanf("%d%d%d", &z, &x, &y);		int r1 = find(x), r2 = find(y);		if (z == 1) {
    			if (r1 != r2) merge(r1, r2);		} else {
    //z == 2			printf("%s\n", r1 == r2 ? "Y" : "N"); 		}	}    return 0;}
   

转载地址：http://oxotf.baihongyu.com/