并查集
Time limit 1000 ms
Mem limit 131072 kB
Description
如题，现在有一个并查集，你需要完成合并和查询操作。
Input
第一行包含两个整数 ,表示共有 个元素和 个操作。
接下来 行，每行包含三个整数 。
当 时，将 与 所在的集合合并。
当 时，输出 与 是否在同一集合内，是的输出
Y ；否则输出 N 。
Output
对于每一个 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。
Sample 1
Input
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
Output
N
Y
N
Y
Hint
对于30%的数据，N≤10，M≤20。
对于70%的数据，N≤100，M≤10^3 。
对于100%的数据，1≤N≤10^4， 1≤M≤2×10^51≤Xi ,Yi≤N，Zi∈{1,2}。
代码
#include <stdio.h>
#include <stdlib.h>
void init(int n); // 初始化并查集
int find(int x); // 查找元素x所在的集合，路径压缩
void un(int x, int y); // 合并元素x和元素y所在的集合
#define MAX 300000
int pa[MAX]; // 表示元素i的父节点
int main(int argc, char *argv[])
{
int N, M, Z, X, Y, i;
scanf("%d %d", &N, &M);
init(N); // 初始化并查集
for (i = 0; i < M; i++)
{
scanf("%d %d %d", &Z, &X, &Y);
if (Z == 1)
{
un(X, Y); // 合并
}
else
{
if (find(X) == find (Y))
{
printf("Y\n");
}
else
{
printf("N\n");
}
}
}
return 0;
}
void init(int n) // 初始化并查集
{
int i;
for (i = 1; i <= n; i++)
{
pa[i] = i;
}
}
int find(int x) // 查找元素x所在的集合，路径压缩
{
if (pa[x] != x)
{
pa[x] = find(pa[x]);
}
return pa[x];
}
void un(int x, int y) // 合并元素x和元素y所在的集合
{
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY)
{
pa[rootX] = rootY;
}
}
