并查集基础篇,配套洛谷3367

并查集是属于数据结构的一种,用来管理元素的一种高效方式,但是不能进行集合的分割 *** 作,可以进行合并 *** 作,最基本有三种 *** 作，合并，查询，初始化.这里就不一一介绍了,可以看下题目来理解一下,当然我采用的是加上rank数组来删减层数和状态压缩过的！

题目描述

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

输入格式

第一行包含两个整数 N,M ,表示共有 N 个元素和MM 个 *** 作。

接下来 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 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

输出 #1复制

N
Y
N
Y

#include
#define max 10005    //定义题目要求的最大个数// 
int N,M;
int a[max],rank[max];
void Init(int n)               //初始化a数组和rank数组// 
{
	for(int i=0;i

其实洛谷并查集那里有好几个题都很相似，大家可以尝试去做一下，熟练一下，比如1551（亲戚）和2078（朋友）

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/563451.html