备战蓝桥杯-并查集

三天不练手生，已经很久没有练习算法题了，今天用我最喜欢的并查集来启动我的算法练习

并查集的三个步骤

1 初始化

2 路径压缩+查询

int find(int x)
{
	if (x != a[x]) a[x] = find(a[x]);
	return a[x];
}

3 合并

void merge(int x, int y)
{
	x = find(x);
	y = find(y);
	if (x != y) a[x] = y;
}

练习题

P3367 【模板】并查集

P3367 【模板】并查集 - 洛谷 | 计算机科学教育新生态

思路：无脑并查集

AC代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define int long long
const int N = 1e6 + 10;
int a[N];
int find(int x)
{
	if (x != a[x]) a[x] = find(a[x]);
	return a[x];
}
void merge(int x, int y)
{
	x = find(x);
	y = find(y);
	if (x != y) a[x] = y;
}
signed main()
{
	int n, m;
	std::cin >> n >> m;
	for (int i = 1;i <= n;i++)
	{
		a[i] = i;
	}
	while (m--)
	{
		int z, x, y;
		std::cin >> z >> x >> y;
		if (z == 1)
		{
			merge(x, y);
		}
		if (z == 2)
		{
			if (find(x) == find(y))
			{
				std::cout << "Y\n";
			}
			else
			{
				std::cout << "N\n";
			}
		}
	}
	return 0;
}

P1551 亲戚

https://www.luogu.com.cn/problem/P1551

无脑模板

AC代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <utility>
#define ing long long
const int N = 5e3 + 10;
int s[N];
int find(int x)
{
	if (x != s[x])s[x] = find(s[x]);
	return s[x];
}
void merge(int x, int y)
{
	x = find(x);
	y = find(y);
	if (x != y)
	{
		s[x] = y;
	}
}
signed main()
{
	int n, m, p;
	std::cin >> n >> m >> p;
	for (int i = 1;i <= n;i++)
	{
		s[i] = i;
	}
	while (m--)
	{
		int x, y;
		std::cin >> x >> y;
		merge(x, y);
	}
	while (p--)
	{
		int x, y;
		std::cin >> x >> y;
		if (find(x) == find(y))
		{
			std::cout << "Yes\n";
		}
		else
			std::cout << "No\n";
	}
	return 0;
}

集合写真

集合写真 - 洛谷 | 计算机科学教育新生态

这道题好像和并查集没什么关系，但是真没想到没写endl居然过不了，后来看了大佬们的题解发现要输出一个endl，暴力即可

AC代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <utility>
#define ing long long
const int N = 50 + 10;
int a[N];
signed main()
{
	int n;
	std::cin >> n;
	for (int i = 1;i <= n;i++)
	{
		std::cin >> a[i];
	}
	int x;
	std::cin >> x;
	int pos = -999;
	for (int i = 1;i <= n;i++)
	{
		if (x < a[i])
		{
			pos = i ;
			break;
		}
	}
	if (pos != -999)
	{
		std::cout << pos<<"\n";
	}
	else
		std::cout << n + 1<<"\n";
	return 0;
}