1. 题目
2. 读题(需要重点注意的东西)
思路:
一句话思路:使用并查集,在其基础上维护它们到根节点的距离,然后计算如下公式:
若x 到根节点的距离为 d[x]
,则:
d[x] % 3 == 0
,说明x和y是同类
d[x] % 3 == 1
,说明x可以吃y
d[x] % 3 == 2
,说明x可以被y吃
x到根节点的距离是d[x],y到根节点的距离是d[y],则x和y的关系怎么判断呢?
x到y的距离为 d[x] - d[y],再代入上述公式:
得到最终的公式:( d[x] - d[y] )% 3
,判断余数即可。
解题过程:
- 初始化每一个点的根节点都是它自己
- 如果输入 1 x y : 首先判断x和y是不是在一个集合里
p[x] == p[y] ?
- 如果是,则判断
(d[x] - d[y]) % 3
是否为0,若不为0,则说明有误,错误数量++ - 否则,将x和y合并为一个集合,即并查集的合并操作,在合并时要注意
※ 1 . 更新距离
- 如果是,则判断
- 如果输入 2 x y : 首先判断x和y是不是在一个集合里
p[x] == p[y] ?
- 如果是,则判断
(d[x] - d[y]) % 3 == 1
是否成立,若不成立,则说明有误,错误数量++ - 如果不在一个集合里,将将x和y合并为一个集合,即并查集的合并操作,在合并时要注意
※ 2 . 更新距离
- 如果是,则判断
- 最后所有的查询对象都在一个集合里,通过每个点到同一个根节点的距离,就能判断某两个点的关系
以上两个距离如何更新?
请下拉,见3.解法
后的两个问题。
3. 解法
---------------------------------------------------解法---------------------------------------------------
/*
d[x] 表示节点x到根节点的路径
若x%3 == 0,则表示与根节点是同类
若x%3 == 1,则表示x可以吃根节点
若x%3 == 2,则表示x被根节点吃
*/
#include <iostream>
using namespace std;
const int N = 50010;
int n, m;
int p[N], d[N]; //p[x]表示:father;d[x]表示:距离。
// 并查集
// 在并查集的基础上维护一个到根节点距离
int find(int x)
{
if (p[x] != x) // 如果x不是树根
{
int t = find(p[x]);
// 先更新d[x],再更新p[x]
d[x] += d[p[x]]; // d[x] 表示x到根节点之间的距离 = x到父节点的距离+父节点到根节点的距离
p[x] = t;
}
return p[x];
}
int main()
{
scanf("%d%d", &n, &m);
// 初始化每一个点
for (int i = 1; i <= n; i ++ ) p[i] = i;
// res表示假话的数量
int res = 0;
while (m -- )
{
// t表示种类:1 or 2
int t, x, y;
scanf("%d%d%d", &t, &x, &y);
// 如果x或者y大于了数量n,说明是假话,res直接加1
if (x > n || y > n) res ++ ;
else
{
// 找出x和y的根节点px、py
int px = find(x), py = find(y);
// 如果t是1,表示x和y是同类
// --------t==1,判断是否是同类-------------
if (t == 1)
{
// 如果x和y的根节点相同,即它们在一个集合里
// 在一个集合里,可以判断,若d[x] - d[y]) % 3 != 0 ,则表示与根节点不是同类
if (px == py && (d[x] - d[y]) % 3) res ++ ;
// 如果x和y不在一个集合里:则合并并查集,让px指向py
// 此时需要x和y是同一类,则需要满足(d[x]+d[px]-d[y])%3 == 0,则d[px]=d[y]-d[x]
else if (px != py)
{
// 合并并查集
p[px] = py;
// 合并后更新d[px]
d[px] = d[y] - d[x];
}
}
// -----------如果t是2,判断能否被吃---------------
else
{
// 先判断是否在一个集合中,然后判断: x吃y,则x比y多1,则(d[x] - d[y] - 1) % 3 == 0
if (px == py && (d[x] - d[y] - 1) % 3) res ++ ;
else if (px != py)
{
// 合并并查集
p[px] = py;
// 因为x要吃y,按照式子,则需要满足(d[x] + d[px] - d[y] - 1 = 0)
// 则 d[px] = d[y] + 1 - d[x]
d[px] = d[y] + 1 - d[x];
}
}
}
}
printf("%d\n", res);
return 0;
}
可能存在的问题(所有问题的位置都在上述代码中标注了出来)
问题一:当t == 1,且 x 和 y 不在一个集合
时,要怎么办?
答:
※ 1 . 更新距离
在此处,我们需要将距离更新,使得x和y是同一类
合并前:
根据并查集的合并方式,我们是将节点x的根节点直接连接到y的根节点上
。
合并后:
因为 x 和 y是同一类,因此必须满足 x 到 y 的距离模 3 为 0
问题二:当t == 2,且 x 和 y 不在一个集合
时,要怎么办?
答:
在此处,我们需要将距离更新,使得x能够吃y
合并前:
合并后:
4. 可能有帮助的前置习题
5. 所用到的数据结构与算法思想
- 并查集
6. 总结
并查集的例题,在并查集的基础上维护到根节点的距离,从而表示能否被吃,理解思想并实现代码。
写得很详细,看懂了 谢谢大佬