C语言-算法-并查集

并查集

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;
	}
}