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

题目描述

输入格式

输出格式

输入输出样例

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

输出 #1

NYNY

说明/提示

对于 $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;}
   

转载地址：https://memcpy0.blog.csdn.net/article/details/108272018 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！