并查集

名称

并查集
Disjoint-set
Union-Find Set
Union-Find Forest

简介

维护$n$个元素，刚开始每个元素自己一个集合，支持两个操作。

• 合并两个元素所在的集合
• 询问两个元素是否在相同的集合内

初始化

int f[1000020];
for (int i = 0; i <= n; i++)
{
	f[i] = i;
	// 比较简单

	f[i] = 0;
	// 有时候也这样实现
}

其他支持：

• 维护每个元素和同一个集合内的其他元素的关系
• 每个元素所在的集合的大小

不带路径压缩的查找函数

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

带路径压缩的查找函数

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

合并两个元素所在的集合

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

时间复杂度

直接实现的话，时间复杂度最坏可以到$O(n)$。
两个常见优化，启发式合并，路径压缩。

• 启发式合并：把大小较小的集合挂在较大的集合上。（有的写法是考虑深度而不是大小）
• 路径压缩：询问过的点到根节点的路径，都直接挂在根节点上。

实现其中任意一个时间复杂度变为$O(\log n)$。
实现其中两个，时间复杂度变为$O(\alpha(n))$，其中$\alpha(n)$是阿克曼函数的反函数，可以认为非常小。

多数情况下为了简单，都实现路径压缩（只需要一句赋值）而不实现启发式合并（需要记录大小）

在某些题目中由于会爆栈，需要使用非递归的find函数。

可持久化与撤销

如果希望支持可持久化（访问历史版本）和撤销最后若干次操作，
那么不能使用路径压缩优化，只使用启发式合并。

对于可持久化，需要使用可持久化数组。

对于撤销最后若干次操作，需要记下每次合并操作，修改了哪个f[x]。

参考题目

并查集:
https://codeforces.com/problemset/problem/1249/B1
https://codeforces.com/problemset/problem/1249/B2
大家传递书互相看，问每个人能看到几本书
交换关系一定是一个环，环长就是答案

https://codeforces.com/problemset/problem/217/A
输入n个点，如果两个点x相同，或者y相同，那么他们属于同一个区域
问一共有多少个区域

https://www.luogu.com.cn/problem/P1551
并查集
这类先输入所有边，再询问的题目
也可以用DFS

P3144 [USACO16OPEN]Closing the Farm S

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

题目背景

本题和 金组同名题目 在题意上一致，唯一的不同是数据范围。

题目描述

FJ 和他的奶牛们正在计划离开小镇做一次长的旅行，同时 FJ 想临时地关掉他的农场以节省一些金钱。

这个农场一共有被用 $M$ 条双向道路连接的 $N$ 个谷仓（$1 \leq N,M \leq 3000$）。为了关闭整个农场，FJ 计划每一次关闭掉一个谷仓。当一个谷仓被关闭了，所有的连接到这个谷仓的道路都会被关闭，而且再也不能够被使用。

FJ 现在正感兴趣于知道在每一个时间（这里的“时间”指在每一次关闭谷仓之前的时间）时他的农场是否是“全连通的”——也就是说从任意的一个开着的谷仓开始，能够到达另外的一个谷仓。注意自从某一个时间之后，可能整个农场都开始不会是“全连通的”。

输入格式

输入第一行两个整数 $N,M$。

接下来 $M$ 行，每行两个整数 $u,v$（$1 \leq u,v \leq N$），描述一条连接 $u,v$ 两个农场的路。

最后 $N$ 行每行一个整数，表示第 $i$ 个被关闭的农场编号。

输出格式

输出 $N$ 行，每行包含 YES 或 NO，表示某个时刻农场是否是全连通的。

第一行输出最初的状态，第 $i$ 行（$2 \leq i \leq N$）输出第 $i-1$ 个农场被关闭后的状态。

样例 #1

样例输入 #1

4 3
1 2
2 3
3 4
3
4
1
2

样例输出 #1

YES
NO
YES
YES

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, s;
vector<int> a[200020];
int f[200020];
int p[200020];
bool v[200020];
bool z[200020];
int F(int x)
{
	return f[x] != x ? f[x] = F(f[x]) : x;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> p[i];
		f[i] = i;
	}
	for (int i = n; i > 0; i--)
	{
		v[p[i]] = true;
		s++;
		for (int j: a[p[i]])
		{
			if (v[j] && F(j) != F(p[i]))
			{
				f[F(j)] = F(p[i]);
				s--;
			}
		}
		z[i] = s == 1;
	}
	for (int i = 1; i <= n; i++)
	{
		printf("%s\n", z[i] ? "YES" : "NO");
	}
	return 0;
}

题解

P6121 [USACO16OPEN]Closing the Farm G

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

题目背景

本题和 银组同名题目 在题意上一致，唯一的不同是数据范围。

题目描述

FJ 和他的奶牛们正在计划离开小镇做一次长的旅行，同时 FJ 想临时地关掉他的农场以节省一些金钱。

这个农场一共有被用 $M$ 条双向道路连接的 $N$ 个谷仓（$1 \leq N,M \leq 2 \times 10^5$）。为了关闭整个农场，FJ 计划每一次关闭掉一个谷仓。当一个谷仓被关闭了，所有的连接到这个谷仓的道路都会被关闭，而且再也不能够被使用。

FJ 现在正感兴趣于知道在每一个时间（这里的“时间”指在每一次关闭谷仓之前的时间）时他的农场是否是“全连通的”——也就是说从任意的一个开着的谷仓开始，能够到达另外的一个谷仓。注意自从某一个时间之后，可能整个农场都开始不会是“全连通的”。

输入格式

输入第一行两个整数 $N,M$。

接下来 $M$ 行，每行两个整数 $u,v$（$1 \leq u,v \leq N$），描述一条连接 $u,v$ 两个农场的路。

最后 $N$ 行每行一个整数，表示第 $i$ 个被关闭的农场编号。

输出格式

输出 $N$ 行，每行包含 YES 或 NO，表示某个时刻农场是否是全连通的。

第一行输出最初的状态，第 $i$ 行（$2 \leq i \leq N$）输出第 $i-1$ 个农场被关闭后的状态。

样例 #1

样例输入 #1

4 3
1 2
2 3
3 4
3
4
1
2

样例输出 #1

YES
NO
YES
YES

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, s;
vector<int> a[200020];
int f[200020];
int p[200020];
bool v[200020];
bool z[200020];
int F(int x)
{
	return f[x] != x ? f[x] = F(f[x]) : x;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> p[i];
		f[i] = i;
	}
	for (int i = n; i > 0; i--)
	{
		v[p[i]] = true;
		s++;
		for (int j: a[p[i]])
		{
			if (v[j] && F(j) != F(p[i]))
			{
				f[F(j)] = F(p[i]);
				s--;
			}
		}
		z[i] = s == 1;
	}
	for (int i = 1; i <= n; i++)
	{
		printf("%s\n", z[i] ? "YES" : "NO");
	}
	return 0;
}

题解

P6111 [USACO18JAN]MooTube S

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

题目背景

本题与 金组同名题目 在题意上一致，唯一的差别是数据范围。

题目描述

在业余时间，Farmer John 创建了一个新的视频共享服务，他将其命名为 MooTube。在 MooTube 上，Farmer John 的奶牛可以录制，分享和发现许多有趣的视频。他的奶牛已经发布了 $N$ 个视频（$1 \leq N \leq 5000$），为了方便将其编号为 $1 \ldots N$ 。然而，FJ 无法弄清楚如何帮助他的奶牛找到他们可能喜欢的新视频。

FJ 希望为每个 MooTube 视频创建一个“推荐视频”列表。这样，奶牛将被推荐与他们已经观看过的视频最相关的视频。

FJ 设计了一个“相关性”度量标准，顾名思义，它确定了两个视频相互之间的相关性。他选择 $N-1$ 对视频并手动计算其之间的相关性。然后，FJ 将他的视频建成一棵树，其中每个视频是节点，并且他手动将 $N-1$ 对视频连接。为了方便，FJ 选择了 $N-1$ 对，这样任意视频都可以通过一条连通路径到达任意其他视频。 FJ 决定将任意一对视频的相关性定义为沿此路径的任何连接的最小相关性。

Farmer John 想要选择一个 $K$ 值，以便在任何给定的 MooTube 视频旁边，推荐所有其他与该视频至少有 $K$ 相关的视频。然而，FJ 担心会向他的奶牛推荐太多的视频，这可能会分散他们对产奶的注意力！因此，他想设定适当的 $K$ 值。 Farmer John希望得到您的帮助，回答有关 $K$ 值的推荐视频的一些问题。

输入格式

第一行输入包含 $N$ 和 $Q$（$1 \leq Q \leq 5000$）。

接下来的 $N-1$ 行描述了 FJ 手动比较的一对视频。 每行包括三个整数 $p_i$，$q_i$ 和 $r_i$（$1 \leq p_i, q_i \leq N$，$1 \leq r_i \leq 10^9$），表示视频 $p_i$ 和 $q_i$ 已连接并且相关性为 $r_i$。

接下来的 $Q$ 行描述了 Farmer John 的 $Q$ 个问题。每行包含两个整数，$k_i$ 和 $v_i$（$1 \leq k_i \leq 10^9$，$1 \leq v_i \leq N$），表示 FJ 的第 $i$ 个问题询问中当 $K = k_i$ 时，第 $v_i$ 个视频推荐列表中将推荐的视频数。

输出格式

输出 $Q$ 行。在第 $i$ 行，输出 FJ 的第 $i$ 个问题的答案。

样例 #1

样例输入 #1

4 3
1 2 3
2 3 2
2 4 4
1 2
4 1
3 1

样例输出 #1

3
0
2

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
pair<int, pair<int, int> > a[200020];
int f[100020];
int c[100020];
int z[100020];
int F(int x)
{
	return f[x] != x ? f[x] = F(f[x]) : x;
}
void U(int x, int y)
{
	x = F(x);
	y = F(y);
	if (x != y)
	{
		f[x] = y;
		c[y] += c[x];
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		f[i] = i;
		c[i] = 1;
	}
	for (int i = 0; i < n - 1; i++)
	{
		scanf("%d%d%d", &a[m + i].second.first, &a[m + i].second.second, &a[m + i].first);
	}
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d", &a[i].first, &a[i].second.second);
		a[i].second.first = -i;
	}
	sort(a, a + m + n - 1);
	for (int i = m + n - 2; i >= 0; i--)
	{
		if (a[i].second.first > 0)
		{
			U(a[i].second.first, a[i].second.second);
		}
		else
		{
			z[-a[i].second.first] = c[F(a[i].second.second)] - 1;
		}
	}
	for (int i = 0; i < m; i++)
	{
		printf("%d\n", z[i]);
	}
	return 0;
}

题解

P6111 [USACO18JAN]MooTube S
P4185 [USACO18JAN]MooTube G
大概思路：
把所有边和所有询问按照关联性从大到小一起排序
如果关联性相同，先排边，再排询问
实现起来，一起排序比较简单

每个结构体包含
类别：询问还是边？
询问：k是多少？v是多少？这是第几个询问
边：起点x，终点y，边权k。

询问 make_pair(k, make_pair(-i -第几个询问, v))
边 make_pair(k, make_pair(x, y))
直接排序的话，边一定排在点的前面

P4185 [USACO18JAN]MooTube G

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

题目背景

本题与 银组同名题目 在题意上一致，唯一的差别是数据范围。

题目描述

在业余时间，Farmer John 创建了一个新的视频共享服务，他将其命名为 MooTube。在 MooTube 上，Farmer John 的奶牛可以录制，分享和发现许多有趣的视频。他的奶牛已经发布了 $N$ 个视频（$1 \leq N \leq 10^5$），为了方便将其编号为 $1 \ldots N$ 。然而，FJ 无法弄清楚如何帮助他的奶牛找到他们可能喜欢的新视频。

FJ 希望为每个 MooTube 视频创建一个“推荐视频”列表。这样，奶牛将被推荐与他们已经观看过的视频最相关的视频。

FJ 设计了一个“相关性”度量标准，顾名思义，它确定了两个视频相互之间的相关性。他选择 $N-1$ 对视频并手动计算其之间的相关性。然后，FJ 将他的视频建成一棵树，其中每个视频是节点，并且他手动将 $N-1$ 对视频连接。为了方便，FJ 选择了 $N-1$ 对，这样任意视频都可以通过一条连通路径到达任意其他视频。 FJ 决定将任意一对视频的相关性定义为沿此路径的任何连接的最小相关性。

Farmer John 想要选择一个 $K$ 值，以便在任何给定的 MooTube 视频旁边，推荐所有其他与该视频至少有 $K$ 相关的视频。然而，FJ 担心会向他的奶牛推荐太多的视频，这可能会分散他们对产奶的注意力！因此，他想设定适当的 $K$ 值。 Farmer John希望得到您的帮助，回答有关 $K$ 值的推荐视频的一些问题。

输入格式

第一行输入包含 $N$ 和 $Q$（$1 \leq Q \leq 10^5$）。

接下来的 $N-1$ 行描述了 FJ 手动比较的一对视频。 每行包括三个整数 $p_i$，$q_i$ 和 $r_i$（$1 \leq p_i, q_i \leq N$，$1 \leq r_i \leq 10^9$），表示视频 $p_i$ 和 $q_i$ 已连接并且相关性为 $r_i$。

接下来的 $Q$ 行描述了 Farmer John 的 $Q$ 个问题。每行包含两个整数，$k_i$ 和 $v_i$（$1 \leq k_i \leq 10^9$，$1 \leq v_i \leq N$），表示 FJ 的第 $i$ 个问题询问中当 $K = k_i$ 时，第 $v_i$ 个视频推荐列表中将推荐的视频数。

输出格式

输出 $Q$ 行。在第 $i$ 行，输出 FJ 的第 $i$ 个问题的答案。

样例 #1

样例输入 #1

4 3
1 2 3
2 3 2
2 4 4
1 2
4 1
3 1

样例输出 #1

3
0
2

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
pair<int, pair<int, int> > a[200020];
int f[100020];
int c[100020];
int z[100020];
int F(int x)
{
	return f[x] != x ? f[x] = F(f[x]) : x;
}
void U(int x, int y)
{
	x = F(x);
	y = F(y);
	if (x != y)
	{
		f[x] = y;
		c[y] += c[x];
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		f[i] = i;
		c[i] = 1;
	}
	for (int i = 0; i < n - 1; i++)
	{
		scanf("%d%d%d", &a[m + i].second.first, &a[m + i].second.second, &a[m + i].first);
	}
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d", &a[i].first, &a[i].second.second);
		a[i].second.first = -i;
	}
	sort(a, a + m + n - 1);
	for (int i = m + n - 2; i >= 0; i--)
	{
		if (a[i].second.first > 0)
		{
			U(a[i].second.first, a[i].second.second);
		}
		else
		{
			z[-a[i].second.first] = c[F(a[i].second.second)] - 1;
		}
	}
	for (int i = 0; i < m; i++)
	{
		printf("%d\n", z[i]);
	}
	return 0;
}

题解

P6111 [USACO18JAN]MooTube S
P4185 [USACO18JAN]MooTube G
大概思路：
把所有边和所有询问按照关联性从大到小一起排序
如果关联性相同，先排边，再排询问
实现起来，一起排序比较简单

每个结构体包含
类别：询问还是边？
询问：k是多少？v是多少？这是第几个询问
边：起点x，终点y，边权k。

询问 make_pair(k, make_pair(-i -第几个询问, v))
边 make_pair(k, make_pair(x, y))
直接排序的话，边一定排在点的前面

P5836 [USACO19DEC]Milk Visits S

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

题目描述

Farmer John 计划建造 $N$ 个农场，用 $N-1$ 条道路连接，构成一棵树（也就是说，所有农场之间都互相可以到达，并且没有环）。每个农场有一头奶牛，品种为更赛牛或荷斯坦牛之一。

Farmer John 的 $M$ 个朋友经常前来拜访他。在朋友 $i$ 拜访之时，Farmer John 会与他的朋友沿着从农场 $A_i$ 到农场 $B_i$ 之间的唯一路径行走（可能有 $A_i = B_i$）。除此之外，他们还可以品尝他们经过的路径上任意一头奶牛的牛奶。由于 Farmer John 的朋友们大多数也是农场主，他们对牛奶有着极强的偏好。他的有些朋友只喝更赛牛的牛奶，其余的只喝荷斯坦牛的牛奶。任何 Farmer John 的朋友只有在他们访问时能喝到他们偏好的牛奶才会高兴。

请求出每个朋友在拜访过后是否会高兴。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$。

第二行包含一个长为 $N$ 的字符串。如果第 $i$ 个农场中的奶牛是更赛牛，则字符串中第 $i$ 个字符为 G，如果第 $i$ 个农场中的奶牛是荷斯坦牛则为 H。

以下 $N-1$ 行，每行包含两个不同的整数 $X$ 和 $Y$（$1 \leq X, Y \leq N$），表示农场 $X$ 与 $Y$ 之间有一条道路。

以下 $M$ 行，每行包含整数 $A_i$，$B_i$，以及一个字符 $C_i$。$A_i$ 和 $B_i$ 表示朋友 $i$ 拜访时行走的路径的端点，$C_i$ 是 G 或 H 之一，表示第 $i$ 个朋友喜欢更赛牛的牛奶或是荷斯坦牛的牛奶。

输出格式

输出一个长为 $M$ 的二进制字符串。如果第 $i$ 个朋友会感到高兴，则字符串的第 $i$ 个字符为 1，否则为 0。

样例 #1

样例输入 #1

5 5
HHGHG
1 2
2 3
2 4
1 5
1 4 H
1 4 G
1 3 G
1 3 H
5 5 H

样例输出 #1

10110

提示

在这里，从农场 1 到农场 4 的路径包括农场 1、2 和 4。所有这些农场里都是荷斯坦牛，所以第一个朋友会感到满意，而第二个朋友不会。

关于部分分：

测试点 $1$ 样例。

测试点 $2\sim 5$ 满足 $N\le 10^3$，$M\le 2\cdot 10^3$。

对于 $100\%$ 的数据，$1 \leq N \leq 10^5$，$1 \leq M \leq 10^5$。

供题：Spencer Compton

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
char s[100020];
vector<int> a[100020];
int f[100020][20];
int c[100020];
int d[100020];
void dfs(int x, int y)
{
	f[x][0] = y;
	d[x] = d[y] + 1;
	c[x] = c[y] + (s[x] == 'G');
	for (int i = 1; i < 20; i++)
	{
		f[x][i] = f[f[x][i - 1]][i - 1];
	}
	for (int i : a[x])
	{
		if (i != y)
		{
			dfs(i, x);
		}
	}
}
int lca(int x, int y)
{
	if (d[x] < d[y])
	{
		swap(x, y);
	}
	int dd = d[x] - d[y];
	for (int i = 0; i < 20; i++)
	{
		if (dd >> i & 1)
		{
			x = f[x][i];
		}
	}
	if (x == y)
	{
		return x;
	}
	for (int i = 20 - 1; i >= 0; i--)
	{
		if (f[x][i] != f[y][i])
		{
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
int main()
{
	scanf("%d%d", &n, &m);
	scanf("%s", s + 1);
	for (int i = 1; i < n; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	dfs(1, 0);
	for (int i = 0; i < m; i++)
	{
		int x, y;
		char o[2];
		scanf("%d%d%s", &x, &y, o);
		int l = lca(x, y);
		int dxy = d[x] + d[y] - 2 * d[l] + 1;
		int cxy = c[x] + c[y] - 2 * c[l] + (s[l] == 'G');
		if (o[0] == 'G')
		{
			printf("%d", cxy > 0);
		}
		else
		{
			printf("%d", cxy < dxy);
		}
	}
	printf("\n");
	return 0;
}

题解

P6004 [USACO20JAN] Wormhole Sort S

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

题目描述

Farmer John 的奶牛们已经厌倦了他对她们每天早上排好序离开牛棚的要求。她们刚刚完成了量子物理学的博士学位，准备将这一过程搞快点。

今天早上，如同往常一样，Farmer John 的 $N$ 头编号为 $1 \ldots N$ 的奶牛（$1 \leq N \leq 10^5$），分散在牛棚中 $N$ 个编号为 $1 \ldots N$ 的不同位置，奶牛 $i$ 位于位置 $p_i$。但是今天早上还出现了 $M$ 个编号为 $1 \ldots M$ 的虫洞（$1 \leq M \leq 10^5$），其中虫洞 $i$ 双向连接了位置 $a_i$ 和 $b_i$，宽度为 $w_i$（$1\le a_i,b_i\le N, a_i\neq b_i, 1\le w_i\le 10^9$）。

在任何时刻，两头位于一个虫洞两端的奶牛可以选择通过虫洞交换位置。奶牛们需要反复进行这样的交换，直到对于 $1 \leq i \leq N$，奶牛 $i$ 位于位置 $i$。

奶牛们不想被虫洞挤坏。帮助她们最大化被她们用来排序的虫洞宽度的最小值。保证奶牛们有可能排好序。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$。

第二行包含 $N$ 个整数 $p_1,p_2,\ldots ,p_N$。保证 $p$ 是 $1 \ldots N$ 的一个排列。

对于 $1$ 到 $M$ 之间的每一个 $i$，第 $i+2$ 行包含整数 $a_i,b_i,w_i$。

输出格式

输出一个整数，为在排序过程中奶牛必须挤进的虫洞的最小宽度的最大值。如果奶牛们不需要用任何虫洞来排序，输出 $-1$。

样例 #1

样例输入 #1

4 4
3 2 1 4
1 2 9
1 3 7
2 3 10
2 4 3

样例输出 #1

9

样例 #2

样例输入 #2

4 1
1 2 3 4
4 2 13

样例输出 #2

-1

提示

样例解释 1

以下是一个仅用宽度至少为 9 的虫洞给奶牛排序的可能方案：

• 奶牛 1 和奶牛 2 使用第三个虫洞交换位置。
• 奶牛 1 和奶牛 3 使用第一个虫洞交换位置。
• 奶牛 2 和奶牛 3 使用第三个虫洞交换位置。

子任务

• 测试点 $3 \sim 5$ 满足 $N,M \leq 1000$。
• 测试点 $6 \sim 10$ 没有额外限制。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
pair<int, pair<int, int> > a[100020];
int p[100020];
int f[100020];
int F(int x)
{
	return f[x] != x ? f[x] = F(f[x]) : x;
}
void U(int x, int y)
{
	f[F(x)] = F(y);
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &p[i]);
		f[i] = i;
	}
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d%d", &a[i].second.first, &a[i].second.second, &a[i].first);
	}
	sort(a, a + m);
	int j = m;
	for (int i = 1; i <= n; i++)
	{
		for (;F(i) != F(p[i]);)
		{
			j--;
			U(a[j].second.first, a[j].second.second);
		}
	}
	printf("%d\n", j == m ? -1 : a[j].first);
	return 0;
}

题解

满足二分
只用 >= x + 1 的虫洞可以，
那么只用 >= x 的虫洞一定也可以

如何判定？

http://www.usaco.org/index.php?page=viewproblem2&cpid=992
P6004 [USACO20JAN]Wormhole Sort S
sort all edges, add them one by one.

3 2 1 4
3 1 2 4
2 1 3 4
1 2 3 4

P5423 [USACO19OPEN]Valleys P

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

题目描述

Bessie 喜欢观光，而今天她正在寻找景色优美的山谷。

她感兴趣的是一个 $N \times N$ 的方阵，其中每个格子都有一个高度。所有在此正方形方阵之外的格子的高度可以被看作是无限大。

山谷指的是一块连续、不含洞的一块区域，并且每个相邻的包围该区域的格子都高于这块区域中的所有格子。

更形式化地说：

• 一组格子被称作是“沿边相邻的”，如果可以从其中任意一个格子出发，经过一些沿上、下、左、右方向的移动，到达其中所有其他格子。
• 一组格子被称作是“沿点相邻的”，如果可以从其中任意一个格子出发，经过一些沿上、下、左、右、对角线方向的移动，到达其中所有其他格子。
• 一个“区域”指的是一组非空并且沿边相邻的格子。
• 一个区域被称作是“有洞的”，如果这个区域的补集（包括在 $N \times N$ 方阵之外的无限高格子）不是沿点相邻的。
• 区域的“边界”指的是所有与该区域内的某个格子正交相邻（上、下、左、右），但本身不在该区域内的格子。
• 一个“山谷”指的是某个非有洞区域，满足区域内的任意格子的高度低于该区域边界上任意格子的高度。

Bessie 的目标是求出所有山谷的大小之和。

一些例子

这是一个区域：

oo.
ooo
..o

这不是一个区域（中间的格子和右下角的格子不沿边相邻）：

oo.
oo.
..o

这是一个非有洞区域：

ooo
o..
o..

这是一个有洞的区域（“甜甜圈”中间的格子与区域外的格子不沿点相邻）：

ooo
o.o
ooo

这是另一个非有洞区域（中间的格子与右下角的格子沿点相邻）：

ooo
o.o
oo.

输入格式

输入的第一行包含 $N$ ，其中 $1 \leq N \leq 750$ 。

以下 $N$ 行每行包含 $N$ 个整数，为方阵每个格子的高度。所有高度 $h$ 满足 $1 \leq h \leq 10^6$ 。所有高度均为不同的整数。

输出格式

输出一个整数，为所有山谷的大小之和。

样例 #1

样例输入 #1

3
1 10 2
20 100 30
3 11 50

样例输出 #1

30

提示

在这个例子中，有三个大小为1的山谷：

o.o
...
o..

一个大小为2的山谷：

...
...
oo.

一个大小为3的山谷：

ooo
...
...

一个大小为6的山谷：

ooo
o..
oo.

一个大小为7的山谷：

ooo
o.o
oo.

以及一个大小为9的山谷：

ooo
ooo
ooo

所以，答案为1 + 1 + 1 + 2 + 3 + 6 + 7 + 9 = 30。

子任务

对于至少19%的测试数据， $N \leq 100$ 。

参考代码

题解

P3101 [USACO14JAN]Ski Course Rating G

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

题目描述

The cross-country skiing course at the winter Moolympics is described by an M x N grid of elevations (1 <= M,N <= 500), each elevation being in the range 0 .. 1,000,000,000.

Some of the cells in this grid are designated as starting points for the course. The organizers of the Moolympics want to assign a difficulty rating to each starting point. The difficulty level of a starting point P should be the minimum possible value of D such that a cow can successfully reach at least T total cells of the grid (1 <= T <= MN), if she starts at P and can only move from cell to adjacent cell if the absolute difference in elevation between the cells is at most D. Two cells are adjacent if one is directly north, south, east, or west of the other.

Please help the organizers compute the difficulty rating for each starting point.

滑雪场用一个M*N(1 <= M,N <= 500)的数字矩阵表示海拔高度，每个数字表示一个范围在0 .. 1,000,000,000的高度。有些格子被指定为起点，组织者想对这些起点做难度评级。

如果起点P点是一个难度级别为D的起点，则D必须是满足以下条件的一个最小值：

（1）从一个格子只能滑到相邻的格子；

（2）这两个格子的海拔差不超过D；

（3）至少能够到达T（1 <= T <= M*N）个格子（包括起点本身）。

输入格式

* Line 1: The integers M, N, and T.

* Lines 2..1+M: Each of these M lines contains N integer elevations.

* Lines 2+M..1+2M: Each of these M lines contains N values that are either 0 or 1, with 1 indicating a cell that is a starting point.

输出格式

* Line 1: The sum of difficulty ratings of all starting points (note that this may not fit into a 32-bit integer, even though individual difficulty ratings will).

样例 #1

样例输入 #1

3 5 10 
20 21 18 99 5 
19 22 20 16 17 
18 17 40 60 80 
1 0 0 0 0 
0 0 0 0 0 
0 0 0 0 1 

样例输出 #1

24 

提示

The ski course is described by a 3 x 5 grid of elevations. The upper-left and lower-right cells are designated as starting points. From each starting point, we must be able to reach at least 10 cells.

The difficulty rating of the upper-left starting point is 4, and for the lower-right it is 20.

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, t, ec;
int a[2500020];
int b[2500020];
int c[2500020];
int f[2500020];
pair<int, pair<int, int> > e[5000020];
int F(int x)
{
	return f[x] != x ? f[x] = F(f[x]) : x;
}
long long z;
void U(int x, int y, long long d)
{
	x = F(x);
	y = F(y);
	if (x != y)
	{
		b[x] += b[y];
		c[x] += c[y];
		if (c[x] >= t)
		{
			z += b[x] * d;
			b[x] = 0;
		}
		f[y] = x;
	}
}
int main()
{
	scanf("%d%d%d", &n, &m, &t);
	for (int i = 0; i < n * m; i++)
	{
		scanf("%d", &a[i]);
	}
	for (int i = 0; i < n * m; i++)
	{
		scanf("%d", &b[i]);
		c[i] = 1;
		f[i] = i;
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 1; j < m; j++)
		{
			e[ec++] = make_pair(abs(a[i * m + j] - a[i * m + j - 1]), make_pair(i * m + j, i * m + j - 1));
		}
	}
	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			e[ec++] = make_pair(abs(a[i * m + j] - a[i * m + j - m]), make_pair(i * m + j, i * m + j - m));
		}
	}
	sort(e, e + ec);
	for (int i = 0; i < ec; i++)
	{
		U(e[i].second.first, e[i].second.second, e[i].first);
	}
	printf("%lld\n", z);
	return 0;
}

题解

P4269 [USACO18FEB]Snow Boots G

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

题目描述

It's winter on the farm, and that means snow! There are $N$ tiles on the path from the farmhouse to the barn, conveniently numbered $1 \dots N$, and tile $i$ is covered in $f_i$ feet of snow.
In his farmhouse cellar, Farmer John has $B$ pairs of boots, numbered $1 \dots B$. Some pairs are more heavy-duty than others, and some pairs are more agile than others. In particular, pair $i$ lets FJ step in snow at most $s_i$ feet deep, and lets FJ move at most $d_i$ forward in each step.

Farmer John starts off on tile $1$ and must reach tile $N$ to wake up the cows. Tile $1$ is sheltered by the farmhouse roof, and tile $N$ is sheltered by the barn roof, so neither of these tiles has any snow. Help Farmer John determine which pairs of snow boots will allow him to make the trek.

输入格式

The first line contains two space-separated integers $N$ and $B$ ($1 \leq N,B \leq 10^5$).
The second line contains $N$ space-separated integers; the $i$th integer is $f_i$, the depth of snow on tile $i$ ($0 \leq f_i \leq 10^9$). It's guaranteed that $f_1 = f_N = 0$.

The next $B$ lines contain two space-separated integers each. The first integer on line $i+2$ is $s_i$, the maximum depth of snow in which pair $i$ can step. The second integer on line $i+2$ is $d_i$, the maximum step size for pair $i$. It's guaranteed that $0 \leq s_i \leq 10^9$ and $1 \leq d_i \leq N-1$.

输出格式

The output should consist of $B$ lines. Line $i$ should contain a single integer: $1$ if Farmer John can trek from tile $1$ to tile $N$ wearing the $i$th pair of boots, and $0$ otherwise.

样例 #1

样例输入 #1

8 7
0 3 8 5 6 9 0 0
0 5
0 6
6 2
8 1
10 1
5 3
150 7

样例输出 #1

0
1
1
0
1
1
1

提示

Problem credits: Dhruv Rohatgi

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
pair<pair<int, int>, int> a[200020];
int c[200020];
int f[200020];
int v[200020];
int z[200020];
int maxsize;
int F(int x)
{
	return f[x] != x ? f[x] = F(f[x]) : x;
}
void U(int x, int y)
{
	x = F(x);
	y = F(y);
	c[x] += c[y];
	f[y] = x;
	maxsize = max(maxsize, c[x]);
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[m + i].first.first);
		a[m + i].second = i + 1;
	}
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d", &a[i].first.first, &a[i].first.second);
		a[i].second = i;
	}
	sort(a, a + n + m);
	for (int i = n + m - 1; i >= 0; i--)
	{
		if (a[i].first.second > 0)
		{
			z[a[i].second] = maxsize < a[i].first.second;
		}
		else
		{
			v[a[i].second] = 1;
			c[a[i].second] = 1;
			maxsize = max(maxsize, 1);
			f[a[i].second] = a[i].second;
			if (v[a[i].second - 1])
			{
				U(a[i].second, a[i].second - 1);
			}
			if (v[a[i].second + 1])
			{
				U(a[i].second, a[i].second + 1);
			}
		}
	}
	for (int i = 0; i < m; i++)
	{
		printf("%d\n", z[i]);
	}
	return 0;
}

题解

P1196 [NOI2002] 银河英雄传说

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

题目背景

公元 $5801$ 年，地球居民迁至金牛座 $\alpha$ 第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。

宇宙历 $799$ 年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。

题目描述

杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成 $30000$ 列，每列依次编号为 $1, 2,\ldots ,30000$。之后，他把自己的战舰也依次编号为 $1, 2, \ldots , 30000$，让第 $i$ 号战舰处于第 $i$ 列，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为 M i j，含义为第 $i$ 号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第 $j$ 号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。

然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。

在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第 $i$ 号战舰与第 $j$ 号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。

作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。

输入格式

第一行有一个整数 $T$（$1 \le T \le 5 \times 10^5$），表示总共有 $T$ 条指令。

以下有 $T$ 行，每行有一条指令。指令有两种格式：

1. M i j：$i$ 和 $j$ 是两个整数（$1 \le i,j \le 30000$），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第 $i$ 号战舰与第 $j$ 号战舰不在同一列。

2. C i j：$i$ 和 $j$ 是两个整数（$1 \le i,j \le 30000$），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。

输出格式

依次对输入的每一条指令进行分析和处理：

• 如果是杨威利发布的舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息。
• 如果是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第 $i$ 号战舰与第 $j$ 号战舰之间布置的战舰数目。如果第 $i$ 号战舰与第 $j$ 号战舰当前不在同一列上，则输出 $-1$。

样例 #1

样例输入 #1

4
M 2 3
C 1 2
M 2 4
C 4 2

样例输出 #1

-1
1

提示

战舰位置图：表格中阿拉伯数字表示战舰编号

参考代码

#include <bits/stdc++.h>
using namespace std;
int f[30020];
int b[30020];
int c[30020];
int F(int x) {
	if (f[x] == x) {
		return x;
	}
	int fx = F(f[x]);
	b[x] += b[f[x]];
	f[x] = fx;
	return f[x];
}
void U(int x, int y) {
	x = F(x);
	y = F(y);
	if (x != y) {
		f[x] = y;
		b[x] = c[y];
		c[y] += c[x];
	}
}
int main() {
	for (int i = 1; i <= 30000; i++) {
		f[i] = i;
		c[i] = 1;
		b[i] = 0;
	}
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		char o;
		int x, y;
		scanf(" %c%d%d", &o, &x, &y);
		if (o == 'M') {
			U(x, y);
		} else if (o == 'C') {
			if (F(x) != F(y)) {
				printf("-1\n");
			} else {
				printf("%d\n", abs(b[x] - b[y]) - 1);
			}
		}
	}
	return 0;
}

题解

并查集，维护信息

每个集合的根节点，就是第一个战舰
对于每个集合需要维护集合大小
对于每个点，需要维护这个点到这个点父亲节点中间有多少个战舰
在压缩路径的同时，维护路径上信息

P1333 瑞瑞的木棍

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

题目描述

瑞瑞有一堆的玩具木棍，每根木棍的两端分别被染上了某种颜色，现在他突然有了一个想法，想要把这些木棍连在一起拼成一条线，并且使得木棍与木棍相接触的两端颜色都是相同的，给出每根木棍两端的颜色，请问是否存在满足要求的排列方式。

例如，如果只有 2 根木棍，第一根两端的颜色分别为 red, blue，第二根两端的颜色分别为 red, yellow，那么 blue---red | red----yellow 便是一种满足要求的排列方式。

输入格式

输入有若干行，每行包括两个单词，表示一根木棍两端的颜色，单词由小写字母组成，且单词长度不会超过 $10$ 个字母，最多有 $250000$ 根木棍。

输出格式

如果木棒能够按要求排列，输出 Possible，否则输出 Impossible

样例 #1

样例输入 #1

blue red
red violet
cyan blue
blue magenta
magenta cyan

样例输出 #1

Possible

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, ans;
map<string, int> g;
int d[500020];
int f[500020];
int get(string s) {
	if (g.find(s) == g.end()) {
		g[s] = n;
		f[n] = n;
		n++;
	}
	return g[s];
}
int F(int x) {
	return f[x] != x ? f[x] = F(f[x]) : x;
}
int main() {
	string a, b;
	while (cin >> a >> b) {
		int x = get(a);
		int y = get(b);
		d[x]++;
		d[y]++;
		f[F(x)] = F(y);
	}
	for (int i = 0; i < n; i++) {
		if (F(i) != F(0)) {
			printf("Impossible\n");
			return 0;
		}
		if (d[i] & 1) {
			ans++;
		}
	}
	if (ans > 2) {
		printf("Impossible\n");
		return 0;
	}
	printf("Possible\n");
	return 0;
}

题解

一笔画的条件

1. 度数为奇数的点 <= 2 个
2. 所有边连通，可以有孤立的点

int get(string s) {
	if (g.find(s) == g.end()) {
		g[s] = n;
		f[n] = n;
		n++;
	}
	return g[s];
}

g.size()==0
g[2] = 123
map在没有的时候，会插入
g.size()==1

int get(string s) {
	if (g.find(s) == g.end()) {
		g[s] = g[s].size();
		// 那么g[s]是多少？
		// 未定义行为，不要这么写
		// 有可能是插入之前的size，
		// 有可能是插入之后的size
	}
	return g[s];
}

P1455 搭配购买

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

题目描述

明天就是母亲节了，电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢？听说在某个网站上有卖云朵的，小朋友们决定一同前往去看看这种神奇的商品，这个店里有 $n$ 朵云，云朵已经被老板编号为 $1,2,3,...,n$，并且每朵云都有一个价值，但是商店的老板是个很奇怪的人，他会告诉你一些云朵要搭配起来买才卖，也就是说买一朵云则与这朵云有搭配的云都要买，电脑组的你觉得这礼物实在是太新奇了，但是你的钱是有限的，所以你肯定是想用现有的钱买到尽量多价值的云。

输入格式

第一行输入三个整数，$n,m,w$，表示有 $n$ 朵云，$m$ 个搭配和你现有的钱的数目。

第二行至 $n+1$ 行，每行有两个整数， $c_i,d_i$，表示第 $i$ 朵云的价钱和价值。

第 $n+2$ 至 $n+1+m$ 行 ，每行有两个整数 $u_i,v_i$。表示买第 $u_i$ 朵云就必须买第 $v_i$ 朵云,同理，如果买第 $v_i$ 朵就必须买第 $u_i$ 朵。

输出格式

一行，表示可以获得的最大价值。

样例 #1

样例输入 #1

5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2

样例输出 #1

1

提示

• 对于 $30\%$ 的数据，满足 $1 \le n \le 100$；
• 对于 $50\%$ 的数据，满足 $1 \le n,w \le 10^3$，$1 \le m \le 100$；
• 对于 $100\%$ 的数据，满足 $1 \le n \le 10^4$，$0 \le m \le 5 \times 10^3$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, w;
int c[10020];
int d[10020];
int f[10020];
int dp[10020];
int F(int x) {
	return f[x] != x ? f[x] = F(f[x]) : x;
}
int main() {
	cin >> n >> m >> w;
	for (int i = 1; i <= n; i++) {
		cin >> c[i] >> d[i];
		f[i] = i;
	}
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		x = F(x);
		y = F(y);
		if (x != y) {
			c[y] += c[x];
			d[y] += d[x];
			f[x] = y;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (F(i) == i) {
			for (int j = w; j >= c[i]; j--) {
				dp[j] = max(dp[j], dp[j - c[i]] + d[i]);
			}
		}
	}
	cout << dp[w] << endl;
}

题解

P1525 [NOIP2010 提高组] 关押罪犯

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

题目描述

S 城现有两座监狱，一共关押着 $N$ 名罪犯，编号分别为 $1-N$。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为 $c$ 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 $c$ 的冲突事件。

每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

在详细考察了$N$ 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。

那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

输入格式

每行中两个数之间用一个空格隔开。第一行为两个正整数 $N,M$，分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的 $M$ 行每行为三个正整数 $a_j,b_j,c_j$，表示 $a_j$ 号和 $b_j$ 号罪犯之间存在仇恨，其怨气值为 $c_j$。数据保证 $1<a_j\leq b_j\leq N, 0 < c_j\leq 10^9$，且每对罪犯组合只出现一次。

输出格式

共 $1$ 行，为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出 0。

样例 #1

样例输入 #1

4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884

样例输出 #1

3512

提示

【输入输出样例说明】罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是 $3512$（由 $2$ 号和 $3$ 号罪犯引发）。其他任何分法都不会比这个分法更优。

【数据范围】

对于 $30\%$的数据有 $N\leq 15$。

对于 $70\%$ 的数据有 $N\leq 2000,M\leq 50000$。

对于 $100\%$ 的数据有 $N\leq 20000,M\leq 100000$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int f[40020];
int n, m;
pair<int, pair<int, int> > a[100020];
int F(int x) {
	if (f[x] == x) {
		return x;
	}
	f[x] = F(f[x]);
	return f[x];
}
void U(int x, int y) {
	x = F(x);
	y = F(y);
	f[x] = y;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= 2 * n; i++) {
		f[i] = i;
	}
	for (int i = 0; i < m; i++) {
		cin >> a[i].second.first >> a[i].second.second >> a[i].first;
	}
	sort(a, a + m);
	for (int i = m - 1; i >= 0; i--) {
		U(a[i].second.first, a[i].second.second + n);
		U(a[i].second.second, a[i].second.first + n);
		if (F(a[i].second.first) == F(a[i].second.first + n)) {
			cout << a[i].first << endl;
			return 0;
		}
	}
	cout << 0 << endl;
	return 0;
}

题解

排序，用并查集判断二分图

问能不能把所有存在仇恨的罪犯都分开？
罪犯看做点，仇恨看做边，是一个二分图
判断是不是二分图 => 判断有没有长度为奇数的环

1. DFS/BFS
2. 并查集

并查集可以拆点，或者关系型并查集
点i拆成i和i+n，
如果x和y不在一个集合中
那么
x和y+n合并
x+n和y合并

可以结合二分通过这个题目
如果使用并查集，直接排序边，一条一条边加入，不需要二分。

4 6
1 2 28351
3 4 12884
1 3 6618
2 3 3512
1 4 2534
2 4 1805

P1536 村村通

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

题目描述

某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 "村村通工程" 的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？

输入格式

输入包含若干组测试测试数据，每组测试数据的第一行给出两个用空格隔开的正整数，分别是城镇数目 $n$ 和道路数目 $m$ ；随后的 $m$ 行对应 $m$ 条道路，每行给出一对用空格隔开的正整数，分别是该条道路直接相连的两个城镇的编号。简单起见，城镇从 $1$ 到 $n$ 编号。

注意：两个城市间可以有多条道路相通。

输出格式

对于每组数据，对应一行一个整数。表示最少还需要建设的道路数目。

样例 #1

样例输入 #1

4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0

样例输出 #1

1
0
2
998

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1 \le n < 1000$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
int f[1020];
int n, m;
int F(int x) {
	if (f[x] == x) {
		return x;
	}
	f[x] = F(f[x]);
	return f[x];
}
int main() {
	while (true) {
		cin >> n;
		if (n == 0) {
			break;
		}
		cin >> m;
		for (int i = 1; i <= n; i++) {
			f[i] = i;
		}
		int cnt = n;
		for (int i = 0; i < m; i++) {
			int x, y;
			cin >> x >> y;
			x = F(x);
			y = F(y);
			if (x != y) {
				f[x] = y;
				cnt--;
			}
		}
		cout << cnt - 1 << endl;
	}
	return 0;
}

题解

并查集，数连通块，也可以DFS/BFS

int cnt = 0;
for (int i = 1; i <= n; i++)
{
if (F(i) == i) // 如果i是一个根节点
{
cnt++;
}
}
也可以数连通块的个数

P1551 亲戚

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

题目背景

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

题目描述

规定：$x$ 和 $y$ 是亲戚，$y$ 和 $z$ 是亲戚，那么 $x$ 和 $z$ 也是亲戚。如果 $x$，$y$ 是亲戚，那么 $x$ 的亲戚都是 $y$ 的亲戚，$y$ 的亲戚也都是 $x$ 的亲戚。

输入格式

第一行：三个整数 $n,m,p$，（$n,m,p \le 5000$），分别表示有 $n$ 个人，$m$ 个亲戚关系，询问 $p$ 对亲戚关系。

以下 $m$ 行：每行两个数 $M_i$，$M_j$，$1 \le M_i,~M_j\le N$，表示 $M_i$ 和 $M_j$ 具有亲戚关系。

接下来 $p$ 行：每行两个数 $P_i,P_j$，询问 $P_i$ 和 $P_j$ 是否具有亲戚关系。

输出格式

$p$ 行，每行一个 Yes 或 No。表示第 $i$ 个询问的答案为“具有”或“不具有”亲戚关系。

样例 #1

样例输入 #1

6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6

样例输出 #1

Yes
Yes
No

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int f[5020];
int n, m, q, x, y;
int F(int x) {
	if (f[x] == x) {
		return x;
	}
	f[x] = F(f[x]);
	return f[x];
}
int main() {
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++) {
		f[i] = i;
	}
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		f[F(x)] = F(y);
	}
	for (int i = 0; i < q; i++) {
		cin >> x >> y;
		if (F(x) == F(y)) {
			printf("Yes\n");
		} else {
			printf("No\n");
		}
	}
	return 0;
}

题解

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

并查集，因为所有边是先给定的，所以也可以DFS/BFS

2种做法

1. 并查集，读入一条边合并一条边 O(m \alpha(n))
2. DFS/BFS，读入之后存边，最后一起DFS/BFS O(n + m)
   理论上第二种更快，但是需要存边
   第一种更好写

Tips:

1. if all edges are given before queries, then BFS/DFS is the same union find set

BFS/DFS is faster. O(n + m)
union find set. O(m * alpha(n))
We do not need to record the edges.

先合并，再询问

1. BFS/DFS
2. 并查集

理论上 BFS/DFS 更快
但是大家都会写 并查集
因为 BFS/DFS 需要存边

P1955 [NOI2015] 程序自动分析

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

题目描述

在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本：假设 $x_1,x_2,x_3,\cdots$ 代表程序中出现的变量，给定 $n$ 个形如 $x_i=x_j$ 或 $x_i\neq x_j$ 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：$x_1=x_2,x_2=x_3,x_3=x_4,x_4\neq x_1$，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。

现在给出一些约束满足问题，请分别对它们进行判定。

输入格式

输入的第一行包含一个正整数 $t$，表示需要判定的问题个数。注意这些问题之间是相互独立的。

对于每个问题，包含若干行：

第一行包含一个正整数 $n$，表示该问题中需要被满足的约束条件个数。接下来 $n$ 行，每行包括三个整数 $i,j,e$，描述一个相等/不等的约束条件，相邻整数之间用单个空格隔开。若 $e=1$，则该约束条件为 $x_i=x_j$。若$e=0$，则该约束条件为 $x_i\neq x_j$。

输出格式

输出包括 $t$ 行。

输出文件的第 $k$ 行输出一个字符串 YES 或者 NO（字母全部大写），YES 表示输入中的第 $k$ 个问题判定为可以被满足，NO 表示不可被满足。

样例 #1

样例输入 #1

2
2
1 2 1
1 2 0
2
1 2 1
2 1 1

样例输出 #1

NO
YES

样例 #2

样例输入 #2

2
3
1 2 1
2 3 1
3 1 1
4
1 2 1
2 3 1
3 4 1
1 4 0

样例输出 #2

YES
NO

提示

【样例解释1】

在第一个问题中，约束条件为：$x_1=x_2,x_1\neq x_2$。这两个约束条件互相矛盾，因此不可被同时满足。

在第二个问题中，约束条件为：$x_1=x_2,x_1 = x_2$。这两个约束条件是等价的，可以被同时满足。

【样例说明2】

在第一个问题中，约束条件有三个：$x_1=x_2,x_2= x_3,x_3=x_1$。只需赋值使得 $x_1=x_2=x_3$，即可同时满足所有的约束条件。

在第二个问题中，约束条件有四个：$x_1=x_2,x_2= x_3,x_3=x_4,x_4\neq x_1$。由前三个约束条件可以推出 $x_1=x_2=x_3=x_4$，然而最后一个约束条件却要求 $x_1\neq x_4$，因此不可被满足。

【数据范围】

注：实际上 $n\le 10^6$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
int t, n;
int a[100020];
int b[100020];
int c[100020];
map<int, int> f;
int F(int x) {
	if (f[x] == 0 || f[x] == x) {
		return x;
	}
	return f[x] = F(f[x]);
}
void U(int x, int y) {
	x = F(x);
	y = F(y);
	f[x] = y;
}
bool ok() {
	for (int i = 0; i < n; i++) {
		if (c[i] == 1) {
			U(a[i], b[i]);
		}
	}
	for (int i = 0; i < n; i++) {
		if (c[i] == 0) {
			if (F(a[i]) == F(b[i])) {
				return false;
			}
		}
	}
	return true;
}
int main() {
	cin >> t;
	for (int tt = 0; tt < t; tt++) {
		cin >> n;
		f.clear();
		for (int i = 0; i < n; i++) {
			cin >> a[i] >> b[i] >> c[i];
		}
		if (ok()) {
			cout << "YES" << endl;
		} else {
			cout << "NO" << endl;
		}
	}
	return 0;
}

题解

并查集，用map当数组，不初始化。

多组数据
map<int, int> 当做数组来用
通过使用函数避免flag变量

map离散化点的标号

P2024 [NOI2001] 食物链

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

题目描述

动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。

现有 N 个动物，以 1 － N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 N 个动物所构成的食物链关系进行描述：

• 第一种说法是 1 X Y，表示 X 和 Y 是同类。
• 第二种说法是2 X Y，表示 X 吃 Y 。

此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

• 当前的话与前面的某些真的话冲突，就是假话
• 当前的话中 X 或 Y 比 N 大，就是假话
• 当前的话表示 X 吃 X，就是假话

你的任务是根据给定的 N 和 K 句话，输出假话的总数。

输入格式

第一行两个整数，N，K，表示有 N 个动物，K 句话。

第二行开始每行一句话（按照题目要求，见样例）

输出格式

一行，一个整数，表示假话的总数。

样例 #1

样例输入 #1

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

样例输出 #1

3

提示

1 ≤ N ≤ 5 ∗ 10^4

1 ≤ K ≤ 10^5

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, k, ans;
int f[150020];
int F(int x) {
	return f[x] != x ? f[x] = F(f[x]) : x;
}
void U(int x, int y) {
	x = F(x);
	y = F(y);
	f[x] = y;
}
int main() {
	cin >> n >> k;
	for (int i = 1; i <= 3 * n; i++) {
		f[i] = i;
	}
	for (int i = 0; i < k; i++) {
		int o, x, y;
		cin >> o >> x >> y;
		if (x > n || y > n) {
			ans++;
		} else {
			if (o == 1) {
				if (F(x) == F(y + n) || F(x) == F(y + 2 * n)) {
					ans++;
				} else {
					U(x, y);
					U(x + n, y + n);
					U(x + 2 * n, y + 2 * n);
				}
			} else {
				if (F(x) == F(y) || F(x) == F(y + n)) {
					ans++;
				} else {
					U(x, y + 2 * n);
					U(x + n, y);
					U(x + 2 * n, y + n);
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

题解

x x自己的同类
x+n x吃的同类
x+2*n 吃x的同类
如果合并之后发现了
F(x) == F(x + n) || F(x) == F(x + 2 * n)
就说明当前合并的这一次是假话

关系型并查集，在维护父亲节点的同时维护权值的差

假设每个点有个权值0 1 2
如果x和y是同类，那么d[x] == d[y]
如果x吃y，那么d[x] == (d[y] + 1) % 3
如果y吃x，那么d[x] == (d[y] + 2) % 3

P2170 选学霸

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

题目描述

老师想从 $n$ 名学生中选 $m$ 人当学霸，但有 $k$ 对人实力相当，如果实力相当的人中，一部分被选上，另一部分没有，同学们就会抗议。所以老师想请你帮他求出他该选多少学霸，才能既不让同学们抗议，又与原来的 $m$ 尽可能接近。

输入格式

第一行，三个正整数 $n,m,k$。

第 $2$ 至第 $k$ 行,每行 $2$ 个数，表示一对实力相当的人的编号（编号为 $1,2,...,n$）。

输出格式

一行，表示既不让同学们抗议，又与原来的 $m$ 尽可能接近的选出学霸的数目。

如果有两种方案与 $m$ 的差的绝对值相等，选较小的一种。

样例 #1

样例输入 #1

4 3 2
1 2
3 4

样例输出 #1

2

提示

对于 $100\%$ 的数据，满足 $1 \le n,m \le 2 \times 10^4$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, l, z;
int c[20020];
bitset<20020> dp;
int f[20020];
int F(int x) {
	return f[x] != x ? f[x] = F(f[x]) : x;
}
int main() {
	cin >> n >> l >> m;
	for (int i = 1; i <= n; i++) {
		f[i] = i;
		c[i] = 1;
	}
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		x = F(x);
		y = F(y);
		if (x != y) {
			c[y] += c[x];
			f[x] = y;
		}
	}
	dp[0] = 1;
	for (int i = 1; i <= n; i++) {
		if (F(i) == i) {
			dp |= dp << c[i];
		}
	}
	for (int i = 0; i <= n; i++) {
		if (dp[i] && abs(z - l) > abs(i - l))
		{
			z = i;
		}
	}
	cout << z << endl;
	return 0;
}

题解

P2256 一中校运会之百米跑

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

题目背景

在一大堆秀恩爱的 ** 之中，来不及秀恩爱的苏大学神踏着坚定（？）的步伐走向了 $100$ 米跑的起点。这时苏大学神发现，百米赛跑的参赛同学实在是太多了，连体育老师也忙不过来。这时体育老师发现了身为体育委员的苏大学神，便来找他帮忙。

可是苏大学神需要热身，不然跑到一半就会抽（筋）、于是他就找到了你。。。如果你帮助体育老师解决了问题，老师就会给你 $5$ 个积分。

题目描述

假设一共有 $N$（$2\leq N\leq 2\times 10^4$）个参赛选手。（尼玛全校学生都没这么多吧）

老师会告诉你这 $N$ 个选手的名字。

接着会告诉你 $M$（$1\leq M\leq 10^6$）句话，即告诉你学生 A 与学生 B 在同一个组里。

如果学生 A 与学生 B 在同一组里，学生 B 与学生 C 也在同一组里，就说明学生 A 与学生 C 在同一组。

然后老师会问你 $K$（$1\leq K\leq 10^6$）句话，即学生 X 和学生 Y 是否在同一组里。

若是则输出 Yes.，否则输出 No.。

输入格式

第一行输入 $N$ 和 $M$。

接下来 $N$ 行输入每一个同学的名字。

再往下 $M$ 行每行输入两个名字，且保证这两个名字都在上面的 $N$ 行中出现过，表示这两个参赛选手在同一个组里。

再来输入 $K$。

接下来输入 $K$ 个体育老师的询问。

输出格式

对于每一个体育老师的询问，输出 Yes. 或 No.。

样例 #1

样例输入 #1

10 6
Jack
Mike
ASDA
Michel
brabrabra
HeHe
HeHE
papapa
HeY
Obama
Jack Obama
HeHe HeHE
brabrabra HeHe
Obama ASDA
papapa Obama
Obama HeHE
3
Mike Obama
HeHE Jack
papapa brabrabra

样例输出 #1

No.
Yes.
Yes.

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int f[20020];
map<string, int> g;
int F(int x) {
	return f[x] != x ? f[x] = F(f[x]) : x;
}
void U(int x, int y) {
	x = F(x);
	y = F(y);
	f[x] = y;
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		g[s] = i;
		f[i] = i;
	}
	for (int i = 0; i < m; i++) {
		string a, b;
		cin >> a >> b;
		U(g[a], g[b]);
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		string a, b;
		cin >> a >> b;
		if (F(g[a]) == F(g[b])) {
			cout << "Yes." << endl;
		} else {
			cout << "No." << endl;
		}
	}
	return 0;
}

题解

map<string, int>
如果太慢的话，就换成 hash

map把字符串映射为数字，并查集。

P2391 白雪皑皑

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

题目背景

“柴门闻犬吠，风雪夜归人”，冬天，不期而至。千里冰封，万里雪飘。空中刮起了鸭毛大雪。雪花纷纷，降落人间。 美能量星球（pty 在 spore 上的一个殖民地）上的人们被这美景所震撼。但是 pty 却不高兴，他不喜欢白色的世界，他觉得这样太单调了。所以他想对雪花进行染色，让世界变得多彩些。

题目描述

现在有 $n$ 片雪花排成一列。 pty 要对雪花进行 $m$ 次染色操作，第 $i$ 次染色操作中，把第 $((i\times p+q)\bmod n)+1$ 片雪花和第 $((i\times q+p)\bmod n)+1$ 片雪花之间的雪花（包括端点）染成颜色 $i$。其中 $p,q$ 是给定的两个正整数。他想知道最后 $n$ 片雪花被染成了什么颜色。没有被染色输出 $0$。

输入格式

输入共四行，每行一个整数，分别为 $n,m,p,q$，意义如题中所述。

输出格式

输出共 $n$ 行，每行一个整数，第 $i$ 行表示第 $i$ 片雪花的颜色。

样例 #1

样例输入 #1

4
3
2
4

样例输出 #1

2
2
3
0

提示

• 对于 $20\%$ 的数据满足：$n,m\leq 1000$。
• 对于 $40\%$ 的数据满足：$n\leq 8000$，$m\leq 10^6$。
• 对于 $80\%$ 的数据满足：$n\leq 5\times 10^5$，$m\leq 10^7$。
• 对于 $100\%$ 的数据满足：$1\leq n\leq 10^6$，$1\leq m\leq 10^7$。

保证 $1\leq m\times p+q,m\times q+p\leq 2\times 10^9$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int f[1000020];
int c[1000020];
int n, m, p, q;
int F(int x)
{
	int r = x;
	while (r != f[r])
	{
		r = f[r];
	}
	while (x != f[x])
	{
		int p = f[x];
		f[x] = r;
		x = p;
	}
	return r;
}
int main()
{
	scanf("%d%d%d%d", &n, &m, &p, &q);
	for (int i = 1; i <= n + 1; i++)
	{
		f[i] = i;
	}
	for (int i = m; i > 0; i--)
	{
		int x = (i * p + q) % n + 1;
		int y = (i * q + p) % n + 1;
		if (x > y)
		{
			swap(x, y);
		}
		for (int j = F(x); j <= y; j = F(j))
		{
			c[j] = i;
			f[j] = j + 1;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		printf("%d\n", c[i]);
	}
	return 0;
}

题解

P2391 白雪皑皑
4个点 3个操作
0 0 0 0
第一个 3 3
0 0 1 0
第二个 1 3
2 2 2 0
第三个 3 3
2 2 3 0

0 0 0 0
0 0 3 0
2 2 3 0
2 2 3 0

倒序操作，如果一个点已经被染色了，就直接跳过。
需要快速地找到区间中下一个未被染色的是哪个
如果一个点没有被染色 f[i] = i
如果一个点被染色了 f[i] = i + 1
用类似并查集找根节点，压缩路径的方法，可以快速找到下一个未被染色的点
并查集可能会爆栈
递归的函数，层数特别多，会爆栈
void dfs(int x)
{
printf("%d\n", x);
dfs(x+1);
}
int main()
{
dfs(0);
}
爆栈怎么办？

1. 有一些OJ会开栈 --Wl,stack=262144
2. 非递归

https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Path_compression
Path compression
Path halving
Path splitting

int F(int x)
{
while (f[x] != x)
{
f[x] = f[f[x]];
x = f[x];
}
return x;
}
不要写 x = f[x] = f[f[x]]
x = 1
int f[3] = {0, 0, 0}

x = f[x] = 2;
修改的是f[1]还是f[2]？
在C++中修改的是f[1]
在Python中修改的是f[2]
是有区别的，避免这么写

P3367 【模板】并查集

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

题目描述

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

输入格式

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

接下来 $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

样例输入 #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

提示

对于 $30\%$ 的数据，$N \le 10$，$M \le 20$。

对于 $70\%$ 的数据，$N \le 100$，$M \le 10^3$。

对于 $100\%$ 的数据，$1\le N \le 10^4$，$1\le M \le 2\times 10^5$，$1 \le X_i, Y_i \le N$，$Z_i \in \{ 1, 2 \}$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int f[10020];
int n, m, x, y, z;
int F(int x) {
	if (f[x] == x) {
		return x;
	}
	f[x] = F(f[x]);
	return f[x];
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		f[i] = i;
	}
	for (int i = 0; i < m; i++) {
		cin >> z >> x >> y;
		if (z == 1) {
			f[F(x)] = F(y);
		} else {
			if (F(x) == F(y)) {
				printf("Y\n");
			} else {
				printf("N\n");
			}
		}
	}
	return 0;
}

题解

模板题，一边合并，一边询问

P3631 [APIO2011]方格染色

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

题目描述

Sam 和他的妹妹 Sara 有一个包含 $n \times m$ 个方格的表格。他们想要将其中的每个方格都染成红色或蓝色。出于个人喜好，他们想要表格中每个 $2 \times 2$ 的方形区域都包含奇数个（ $1$ 个或 $3$ 个）红色方格。例如，下面是一个合法的表格染色方案（R 代表红色，B 代表蓝色）：

B B R B R
R B B B B
R R B R B

可是昨天晚上，有人已经给表格中的一些方格染上了颜色！现在 Sam 和 Sara 非常生气。不过，他们想要知道是否可能给剩下的方格染上颜色，使得整个表格依然满足他们的要求。如果可能的话，满足他们要求的染色方案数有多少呢？

输入格式

输入的第一行包含三个整数 $n,m,k$，分别代表表格的行数，列数和已被染色的方格数目。

之后的 $k$ 行描述已被染色的方格。其中第i行包含三个整数 $x_i,y_i,c_i$，分表代表第 $i$ 个已被染色的方格的行编号、列编号和颜色。$c_i$ 为 $1$ 表示方格被染成红色，$c_i$ 为 $0$ 表示方格被染成蓝色。

输出格式

输出一个整数，表示可能的染色方案数 $w$ 对于 $10^9$ 取模后得到的值。

样例 #1

样例输入 #1

3 4 3
2 2 1
1 2 0
2 3 1

样例输出 #1

8

提示

对于 $20\%$ 的测试数据，$n,m,k \leqslant 5$。

对于 $50\%$ 的测试数据，$n,m \leqslant 5000$，$k \leqslant 25$。

对于 $100\%$ 的测试数据，$2 \leqslant n,m \leqslant 10^5$，$0 \leqslant k \leqslant 10^5$，$1 \leqslant x_i \leqslant n$，$1 \leqslant y_i \leqslant m$，$\forall c_i \in \{0,1\}$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, k, x, y, c;
int f[400020];
int F(int x) {
	return f[x] != x ? f[x] = F(f[x]) : x;
}
void U(int x, int y) {
	x = F(x);
	y = F(y);
	f[x] = y;
}
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < 2 * n + 2 * m; i++) {
		f[i] = i;
	}
	for (int i = 0; i < k; i++) {
		scanf("%d%d%d", &x, &y, &c);
		x--;
		y--;
		if (x % 2 == 1 && y % 2 == 1) {
			c ^= 1;
		}
		if (c == 0) {
			U(x, y + n);
			U(x + n + m, y + n + n + m);
		} else {
			U(x, y + n + n + m);
			U(x + n + m, y + n);
		}
	}
	for (int i = 0; i < n + m; i++) {
		if (F(i) == F(i + n + m)) {
			printf("0\n");
			return 0;
		}
	}
	int cnt = 0;
	for (int i = 0; i < 2 * n + 2 * m; i++) {
		if (F(i) == i) {
			cnt++;
		}
	}
	int ans = 1;
	for (int i = 0; i < cnt / 2 - 1; i++) {
		ans = ans * 2 % 1000000000;
	}
	printf("%d\n", ans);
	return 0;
}

题解

2. 查找 Find

int F(int x)
{
// if (f[x] == x)
// {
// return x;
// }
// return F(f[x]);
return f[x] == x ? x : F(f[x]);
return f[x] == x ? x : f[x] = F(f[x]);
}

int F(int x)
// 查找根节点
{
if (f[x] == x)
// if (f[x] == x || f[x] == 0)
{
return x;
// x 是根
}
return F(f[x]);
// 递归
}

int F(int x)
{
return f[x] != x ? f[x] = F(f[x]) : x;
// return f[x] == x ? x : f[x] = F(f[x]);
// 更新 f[x] to speed up next finding
}
在C++没有区别

在C语言中只有第一种可以编译过

如何解决超时的问题？ （一条长链）

1. 压缩路径
2. 启发式合并/按秩合并
3. 随机合并

只用1. 或者 只用2.
时间复杂度是 log n

1. 和 2. 同时使用，时间复杂度 O(alpha(n))

2. 合并
   // 随机合并
   void U(int x, int y)
   {
   x = F(x);
   // 找到x所在集合的根节点
   y = F(y);
   // 找到y所在集合的根节点

   if (rand() & 1)
   {
   f[x] = y;
   // 把 x 合并到 y 上
   }
   else
   {
   f[y] = x;
   // 把 y 合并到 x 上
   }
   }

C++和C

? 三目运算符
= 赋值
优不同先级
C中 两个优先级相同
return (f[x] == x ? x : f[x]) = F(f[x]);
编译失败

C++
return f[x] == x ? x : (f[x] = F(f[x]));

C++ 可以写 (a ? b : c) = 2
C语言不可以 a + 1 = 2

启发式合并/按秩合并
把小的合并到大的上面

按点数，把小的合并到大的，启发式合并
按深度，把小的合并到大的，按秩合并
随机合并

http://poj.org/problem?id=2395
P1547 [USACO05MAR]Out of Hay S

min(a[1], a[2], ..., a[10]) = 7
min(a[5], a[6], ..., a[19]) = 7
min(a[3], a[4], ..., a[12]) = 8

1 3 8
5 6 9

2 5 7

8 8 8 7 9 9

1 6 7
4 9 7

there must be at least 1 unoccupied cell a[i] (4<=i<=6)
(max_left <= i <= min_right)
(because 7 can only occur once.)

(fill from min_left to max_right, these cells are occupied.)
from 1 to 9, a[i] >= 7

map<int, vector<pair<int, int> > > g;

g[min].push_back(make_pair(left, right))

http://www.usaco.org/index.php?page=viewproblem2&cpid=644
http://www.usaco.org/index.php?page=viewproblem2&cpid=646
P3144 [USACO16OPEN]Closing the Farm S
P6121 [USACO16OPEN]Closing the Farm G

原题只问是否全连通，可以改成问有多少个连通块。
离线 处理

一个一个删除是做不到的
可以倒序考虑，一个一个加入
所有类型删除都可以这样考虑
如果只有删除操作，可以考虑倒序变成加入操作

因为加入的话，连通块个数至多+1，减少多少不一定。

删除一个点很困难
连通块可能减少1个
可能增加很多个

加入一个点很简单
连通块可能增加1个
可能减少很多个

如果只有删除，并且可以离线，那么相当于只有加入。

时间复杂度 O(m log n + n)

solve this problem offline
We can't delete, but we can add them one by one

delete a vertex
the number of components -1
the number of components +?

add a vertex
the number of components +1
the number of components -?

http://www.usaco.org/index.php?page=viewproblem2&cpid=788
http://www.usaco.org/index.php?page=viewproblem2&cpid=789
P6111 [USACO18JAN]MooTube S
P4185 [USACO18JAN]MooTube G
离线 解决这个问题

把所有边排序，询问排序
把所有边从大到小依次加入，中间询问每个连通块的大小

实现：

1. 一起排序

solve this problem offline
sort all edges and queries by relevance

add edges from larger relevance to smaller relevance
each time we query the number of vertices in the component.

http://www.usaco.org/index.php?page=viewproblem2&cpid=968
P5836 [USACO19DEC]Milk Visits S
Is there any H on the path?
is equivalent to
are all letters on the path G?
use union find set to merge adjcent same letters.

http://www.usaco.org/index.php?page=viewproblem2&cpid=950
P5423 [USACO19OPEN]Valleys P

sort (height, x, y) by height increasing, add them one by one
each time the new added and up/down/left/right forms a new valley.
but the new valley might has a hole.

ooo
o.o
ooo

1 + 1 + 1 + 3 + 2 + 6 + 7 + 8 + 9 = 38

count the corners, to detect the hole.

abc
def
ghi

change e from . to o
we need consider
ab
de

bc
ef

de
gh

ef
hi

from
00
00
to
10
00
+1

from
01
00
to
11
00
-1

from
00
01
to
10
01
+1

from
01
10
to
11
10
-3

from
01
01
to
11
01
-1

from
01
11
to
11
11
+1

if the number of corners is 4, then this component should be added to answer

http://www.usaco.org/index.php?page=viewproblem2&cpid=384
P3101 [USACO14JAN]Ski Course Rating G

sort all edges, add them one by one.
maintain the size of each component

I think the number of starting points in the component should be maintained
but the official solution does not.

http://poj.org/problem?id=1988
P2342 [USACO04OPEN]Cube Stacking G

compress the path with information.
the size of each component is also needed.

---

P3631 [APIO2011]方格染色
B B R B R
R B B B B
R R B R B

0 0 1 0 1
1 0 0 0 0
1 1 0 1 0

0 0 1 0 1
1 1 0 1 0
1 1 0 1 0

翻转（行号和列号同时为偶数的位置）位置，变成2x2区域异或为0
事实上，不需要2x2的区域
任意两行，两列，的四个交点都满足这个性质。

A C E G
B D F H

A^BC^D = 0
C^DE^F = 0

A^BE^F = 0

假设表格是空的，问方案数？
第一行 第一列 随便填 其他位置可以推出来
2 ** (n + m - 1)

a[i][j] = x[i]^y[j]
问{x[1 .. n], y[1 .. m]}解数是多少？

假设所有x[i]和y[j]同时取反，a数组并不会变
所以加一个限制y[1] = 0;

P1455 搭配购买
P2170 选学霸
并查集和背包结合在一起

P5836 [USACO19DEC]Milk Visits S

https://www.luogu.com.cn/problem/P4269
P4269 [USACO18FEB]Snow Boots G

Union Find Set
Doubly Linked List

P1111 修复公路
P3958 奶酪
P1197 星球大战

最小生成树
Kruskal
所有边权之和最小
最大边最小
次大边最小
第三大边最小...

P3366 【模板】最小生成树
P1111 修复公路
P2820 局域网
P1547 [USACO05MAR]Out of Hay S
P2126 Mzc家中的男家丁
P1195 口袋的天空
P2121 拆地毯
P1194 买礼物
P1396 营救

abc177_d Friends

https://atcoder.jp/contests/abc177/tasks/abc177_d
有n个人，m个关系，关系有传递性
问n个人至少分成多少个集合
才能让每个集合内的人之间都没有关系

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, z = 1;
int c[200020];
int f[200020];
int F(int x)
{
	return f[x] != x ? f[x] = F(f[x]) : x;
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		f[i] = i;
		c[i] = 1;
	}
	for (int i = 0; i < m; i++)
	{
		cin >> x >> y;
		x = F(x);
		y = F(y);
		if (x != y)
		{
			f[x] = y;
			c[y] += c[x];
			z = max(z, c[y]);
		}
	}
	cout << z << endl;
	return 0;
}

题解

abc120_d Decayed Bridges

https://atcoder.jp/contests/abc120/tasks/abc120_d
n个点，m条边，边一条一条被删掉
问删掉每条边之后有多少对点之间不再互相连通了。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int c[100020];
int f[100020];
int x[100020];
int y[100020];
long long z[100020];
int F(int x)
{
	return f[x] != x ? f[x] = F(f[x]) : x;
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		f[i] = i;
		c[i] = 1;
	}
	for (int i = 0; i < m; i++)
	{
		cin >> x[i] >> y[i];
	}
	for (int i = m - 1; i >= 0; i--)
	{
		z[i] = z[i + 1];
		x[i] = F(x[i]);
		y[i] = F(y[i]);
		if (x[i] != y[i])
		{
			f[x[i]] = y[i];
			z[i] += (long long)c[x[i]] * c[y[i]];
			c[y[i]] += c[x[i]];
		}
	}
	for (int i = 1; i <= m; i++)
	{
		cout << z[0] - z[i] << endl;
	}
	return 0;
}

题解

arc065_b Connectivity

https://atcoder.jp/contests/arc065/tasks/arc065_b
n个点，k条公路，l条铁路
对于每个点，问有多少个点和他
既可以通过公路连接，也可以通过铁路连接

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, k, l, p, q;
int f[200020];
int g[200020];
map<pair<int, int>, int> a;
int F(int x)
{
	return f[x] != x ? f[x] = F(f[x]) : x;
}
int G(int x)
{
	return g[x] != x ? g[x] = G(g[x]) : x;
}
int main()
{
	cin >> n >> k >> l;
	for (int i = 1; i <= n; i++)
	{
		f[i] = i;
		g[i] = i;
	}
	for (int i = 0; i < k; i++)
	{
		cin >> p >> q;
		f[F(p)] = F(q);
	}
	for (int i = 0; i < l; i++)
	{
		cin >> p >> q;
		g[G(p)] = G(q);
	}
	for (int i = 1; i <= n; i++)
	{
		a[make_pair(F(i), G(i))]++;
	}
	for (int i = 1; i <= n; i++)
	{
		cout << a[make_pair(F(i), G(i))] << " ";
	}
	return 0;
}

题解

arc107_c Shuffle Permutation

https://atcoder.jp/contests/arc107/tasks/arc107_c

参考代码

#include <bits/stdc++.h>
using namespace std;
const int p = 998244353;
int n, m;
int a[50][50];
int f[100];
int c[100];
int F(int x)
{
	return f[x] != x ? f[x] = F(f[x]) : x;
}
void U(int x, int y)
{
	x = F(x);
	y = F(y);
	if (x != y)
	{
		f[x] = y;
		c[y] += c[x];
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> a[i][j];
		}
	}
	for (int i = 0; i < 2 * n; i++)
	{
		f[i] = i;
		c[i] = 1;
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			int v = 1;
			for (int k = 0; k < n; k++)
			{
				if (a[i][k] + a[j][k] > m)
				{
					v = 0;
					break;
				}
			}
			if (v)
			{
				U(i, j);
			}
			v = 1;
			for (int k = 0; k < n; k++)
			{
				if (a[k][i] + a[k][j] > m)
				{
					v = 0;
					break;
				}
			}
			if (v)
			{
				U(i + n, j + n);
			}
		}
	}
	long long z = 1;
	for (int i = 0; i < 2 * n; i++)
	{
		if (f[i] == i)
		{
			for (int j = 1; j <= c[i]; j++)
			{
				z = z * j % p;
			}
		}
	}
	cout << z << endl;
	return 0;
}

题解

abc131_f Must Be Rectangular!

https://atcoder.jp/contests/abc131/tasks/abc131_f
输入n个点，如果其中3个点是平行于坐标轴矩形的3个点，那么可以加入第4个点
尽量加更多的点，问至多加多少个点

参考代码

题解

并查集
每个点看做是把x坐标和y坐标合并
每个集合中点数是x坐标个数乘以y坐标个数

CF445B DZY Loves Chemistry

https://codeforces.com/problemset/problem/445/B
https://www.luogu.com.cn/problem/CF445B

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y;
int f[60];
int F(int x)
{
	return f[x] != x ? f[x] = F(f[x]) : x;
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		f[i] = i;
	}
	for (int i = 0; i < m; i++)
	{
		cin >> x >> y;
		x = F(x);
		y = F(y);
		if (x != y)
		{
			f[x] = y;
		}
	}
	int z = n;
	for (int i = 1; i <= n; i++)
	{
		if (f[i] == i)
		{
			z--;
		}
	}
	cout << (1LL << z) << endl;
	return 0;
}

题解

每个化学物质看做一条边，每个连通块大小-1之和是答案

CF1209D Cow and Snacks

https://codeforces.com/problemset/problem/1209/D
https://www.luogu.com.cn/problem/CF1209D

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y;
int f[100020];
int F(int x)
{
	return f[x] != x ? f[x] = F(f[x]) : x;
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		f[i] = i;
	}
	int z = m;
	for (int i = 0; i < m; i++)
	{
		cin >> x >> y;
		x = F(x);
		y = F(y);
		if (x != y)
		{
			f[x] = y;
			z--;
		}
	}
	cout << z << endl;
	return 0;
}

题解

每个guest看做一条边，每个连通块可以满足大小-1个人

CF1213G Path Queries

https://codeforces.com/problemset/problem/1213/G
https://www.luogu.com.cn/problem/CF1213G

参考代码

#include <bits/stdc++.h>
using namespace std;
pair<int, pair<int, int> > a[200020];
int n, m, q;
int w[200020];
int f[200020];
int c[200020];
long long z[200020];
int F(int x)
{
	return f[x] != x ? f[x] = F(f[x]) : x;
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i < n; i++)
	{
		cin >> a[i].second.first >> a[i].second.second >> a[i].first;
	}
	sort(a + 1, a + n);
	for (int i = 1; i <= n; i++)
	{
		f[i] = i;
		c[i] = 1;
	}
	for (int i = 1; i < n; i++)
	{
		int x = F(a[i].second.first);
		int y = F(a[i].second.second);
		z[i] = z[i - 1] + (long long)c[x] * c[y];
		w[i] = a[i].first;
		f[x] = y;
		c[y] += c[x];
	}
	for (int i = 0; i < m; i++)
	{
		cin >> q;
		cout << z[upper_bound(w, w + n, q) - w - 1] << " ";
	}
	return 0;
}

题解

离线kruskal，问多少对点之间连通

CF1411C Peaceful Rooks

https://codeforces.com/problemset/problem/1411/C
https://www.luogu.com.cn/problem/CF1411C

参考代码

#include <bits/stdc++.h>
using namespace std;
int t, n, m, x, y;
int f[100020];
int F(int x)
{
	return f[x] != x ? f[x] = F(f[x]) : x;
}
int main()
{
	cin >> t;
	for (int tt = 0; tt < t; tt++)
	{
		cin >> n >> m;
		for (int i = 1; i <= n; i++)
		{
			f[i] = i;
		}
		int z = m;
		for (int i = 0; i < m; i++)
		{
			cin >> x >> y;
			if (x == y)
			{
				z--;
			}
			else if (F(x) == F(y))
			{
				z++;
			}
			else
			{
				f[F(x)] = F(y);
			}
		}
		cout << z << endl;
	}
	return 0;
}

题解

车 移动主对角线

spoj QN02