题目描述
动物王国中有三类动物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句话有的是真的,有的是假的。
当一句话满足下列三条之一时,这句话就是假话,否则就是真话。
1) 当前的话与前面的某些真的话冲突,就是假话;
2) 当前的话中X或Y比N大,就是假话;
3) 当前的话表示X吃X,就是假话。
你的任务是根据给定的N和K句话,输出假话的总数。
输入格式
第一行是两个整数N和K,以一个空格分隔。
以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。
若D=1,则表示X和Y是同类。
若D=2,则表示X吃Y。
输出格式
只有一个整数,表示假话的数目。
数据范围
1≤N≤50000,
0≤K≤100000
输入样例:
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
输出样例:
3
关注我,不迷路~~~
思路
ok,现在我们讲一讲题目的意思
题目中 A吃B, B吃C,C吃A。
因此有 A<=B B<=C C<=A 形成闭环
可能有小伙伴在看视频的时候有疑惑,比如
A <= B B <= C ??? => 为什么不能推出A <= C 即C能被A吃
你可以想一下,如果 A <= C B <= C 即C能被A吃, C能被B吃,那么A, B不就是同类了吗(相同编号),那A<=B吃显然矛盾了
所以C<=A 即C被A吃
好了,接下来从代码的角度来理解
最头疼的,最核心的还是find()方法
简单的版本可以先看 https://www.acwing.com/file_system/file/content/whole/index/content/1734661/
本节算法
find函数
int find(int x){
if(p[x] != x){
int t = find(p[x]); //记录根节点
d[x] += d[p[x]]; //当前节点到父节点的距离 + 父节点到根节点的距离,为什么,可以看后面的推理,采用回溯思想
p[x] = t; //将当前的节点的父节点置为根节点
}
return p[x];
}
路径压缩,上面只是在压缩的过程中加入了路径的信息
int find(int x){
if(p[x] != x){
int t = find(p[x]); //记录根节点
p[x] = t; //将当前的节点的父节点置为根节点
}
return p[x];
}
以下图为例子
处理find(1)
find(1) p[1] = 2 t = find(2)
find(2) p[2] = 3 t = find(3)
find(3) p[3] = 4 t = find(4)
find(4) p[4] = 4 将p[4]返回
退到上一层
find(3) p[3] = 4 t = 4 d[3] = d[3] + d[4] = 1 + 0 = 1 p[3] = 4 将p[3]返回
退到上一层
find(2) p[2] = 3 t = 4 d[2] = d[2] + d[3] = 2 + 1 = 3 p[2] = 4 将p[2]返回
退到上一层
find(1) p[1] = 2 t = 4 d[1] = d[1] + d[2] = 3 + 3 = 6 p[1] = 4 将p[1]返回
至此,我们发现所有的1,2,3的父节点全部置为了4,实现路径压缩;1,2,3的路径距离也被置为6,3,1 同时也实现了1的父节点的返回
nice!!
了解了find含义
现在我们来看看本算法的约定
约定
食物链是绕不开a <= b b <= c c <= a,
因此,利用边的权重,即当前点到根节点的距离作为约束条件
假设根为a(也可以是b,c,因为这是闭环)
有以下三种情况:
1. a 和 b a <= b b到根节点a的距离为1, a <= b表示b能被a吃掉
2. a 和 c a <= b <= c c到根节点a的距离为2, 实际上a和c的关系为c <= a,即a能被c吃掉
3. a 和 a a <= b <= c <= a a到根节点a的距离为3, 表示a和a是同类关系。
那么你用mod3来识别当前点与根节点之间的关系,如上图所示,1表示和4同类, 2表示被4吃,3表示能够吃4
ok,至此解决了约束问题,进入正轨
初始化
for(int i = 1; i <= n; i ++) p[i] = i;
当前节点到当前节点的距离为0, 同时也表示自己和自己是同类
说假话
1.当前的话中X或Y比N大,就是假话;
2.第一种说法是”1 X Y”,表示X和Y是同类。
这种情况下,
要么说的是假话,即同一个集合下,不满足约定条件
要么说的是真话,1.同一集合下什么事情都不做2.不在同一个集合下,要去实现,来满足约定条件
2.1说的是假话
同一个集合下,不满足约定条件,即当前x的路径值和y的路径值相差的距离不是3的倍数
int px = find(x), py = find(y);
if(t == 1) if(px == py && (d[x] - d[y]) % 3) res ++;
2.2说的是真话
int px = find(x), py = find(y);
if(t == 1){
if(px != py){
p[px] = py;
d[px] = d[y] - d[x]; //更新px到根节点py的距离
}
}
如何去实现约束条件呢
如图所示,px 为 x的根节点, py为 y的根节点, 让px嫁接到py上,那px与py之间的距离为多少才可以满足x和y是同类的约束条件呢?
距离为dis (dx + dis - dy)%3 = 0 => dis = d[y] - d[x]
3. 第二种说法是”2 X Y”,表示X吃Y。
同样有两种情况,要么假的要么真的
3.1 假的
1.如果x吃Y是假的,则说明有冲突的话有 Y吃X, X和Y是同类,即排除真话的可能
int px = find(x), py = find(y);
if(t == 2) if(px == py && (d[x] -d[y] - 1) % 3) res ++;
假设说的是真话 dist = d[x] - d[y] = 1, 只需要将说真话排除即可,即(d[x] -d[y] - 1) % 3 == 0
2.说的是真话,即不在同一个集合,想办法实现
int px = find(x), py = find(y);
if(t == 2){
if(px != py){
p[px] = py;
d[px] = d[y] + 1 - d[x]; //更新px到根节点py的距离
}
}
原理同上,即x与根节点y的距离为1 (d[x] + dist - d[y] - 1) % 3 = 0
dist = d[y] + 1 - d[x]
java
import java.util.Scanner;
public class Main{
static int N = 50010;
static int n, m;
static int[] p = new int[N], d = new int[N];
private static int find(int x) {
if (p[x] != x) {
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 1; i <= n; i++) {
p[i] = i;
}
int res = 0;
while (m -- > 0) {
int t, x, y;
t = sc.nextInt();
x = sc.nextInt();
y = sc.nextInt();
if (x > n || y > n) {
res ++;
} else {
int px = find(x);
int py = find(y);
if (t == 1) {
if (px == py && (d[x] - d[y]) % 3 != 0) {
res ++;
} else if (px != py) {
p[px] = py;
d[px] = d[y] - d[x];
}
} else {
if (px == py && (d[x] - d[y] - 1) % 3 != 0) {
res ++;
} else if (px != py) {
p[px] = py;
d[px] = d[y] + 1 - d[x];
}
}
}
}
System.out.println(res);
}
}
python
N = 50010
p, d = [0] * N, [0] * N
def find(x):
if p[x] != x:
t = find(p[x])
d[x] += d[p[x]]
p[x] = t
return p[x]
def main():
n, m = list(map(int, input().split()))
for i in range(n + 1):
p[i] = i
res = 0
while m:
m -= 1
t, x, y = list(map(int, input().split()))
if x > n or y > n:
res += 1
else:
px, py = find(x), find(y)
if t == 1:
if px == py and (d[x] - d[y]) % 3 != 0:
res += 1
elif px != py:
p[px] = py
d[px] = d[y] - d[x]
else:
if px == py and (d[x] - d[y] - 1) % 3 != 0:
res += 1
elif px != py:
p[px] = py
d[px] = d[y] + 1 - d[x]
print(res)
if __name__ == '__main__':
main()
c++
#include <iostream>
using namespace std;
const int N = 50010;
int n, m;
int p[N], d[N]; //d是节点x到根节点的距离
int find(int x){
if(p[x] != x){
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++) p[i] = i;
int res = 0;
while(m --){
int t, x, y;
scanf("%d%d%d", &t, &x, &y);
if(x > n || y > n) res ++;
else{
int px = find(x), py = find(y); //同一父节点 和 不同父节点之间只差一条线的链接
if(t == 1){
if(px == py && (d[x] - d[y]) % 3) res ++;
else if(px != py){
p[px] = py;
d[px] = d[y] - d[x];
}
}else{
if(px == py && (d[x] -d[y] - 1) % 3) res ++;
else if(px != py){
p[px] = py;
d[px] = d[y] + 1 - d[x];
}
}
}
}
printf("%d", res);
return 0;
}
very clear explain!
靠着海绵宝宝和派大星过活了
大佬,3.2那里为什么不在同一个集合也要合并?
# you are hero!
# I Love You, Bro
想问下d[x]的初始化在哪儿?find函数例子中,d[x]的值都是已经初始化结束的。另外,还想请问下有没有python版本供参考。谢谢!
d[x] 默认都为0,就是自己到自己的距离为0, python版本的一直没空写,哈哈,太忙了
谢谢解答。从你之前的题解学到了很多。thanks a lot! XD
哈哈,谢谢,后续慢慢补充