题目描述
几个问题
- find()方法做了什么
- d[]含义
- 具体代码含义
解答
-
find()方法用于找出当前节点的根节点,在找的过程中,我们用了路径压缩,把路径上的所有节点都指向了根节点,同时更新了每个节点到父节点的距离
-
d[]原本指的是当前节点到父节点的距离,初始化的时候全都是0,因为还没有形成树化结构,都是一个个单独的节点,没有父节点,所以算是0
d[]经过find()方法是发生了变化的,原本指的是当前节点到父节点的距离,然后更新成了每个节点到根节点的距离 -
下面的代码为什么不像以前那么写
int t = find(p[x]); //1
d[x] += d[p[x]]; //2
p[x] = t; //3
注意,在代码1后,我们是不能更新p[x]的值的,因为第二行代码还要用到p[x],如果更新的话,p[x]指向根节点,我们计算的就是d[x] = d[x] + d[root] = 1 + 0;而我们要计算的是d[x] = d[x] + d[p[x]] = 1 + 1;
所以要声明一个变量暂存一下根节点
-
px == py && (d[x] - d[y]) % 3 != 0
代码的含义
px指的是x的根节点,py指的是y的根节点,如果px == py,说明x,y已经在一颗树上了,我们就可以根据距离知道他们之间的关系;
如果x,y是同类,那他们到根节点的距离应该是三个倍数,那d[x] - d[y]也应该是3的倍数,比如说3和6,6-3=3也是3的倍数
3的倍数%3余数应该是0,但是如果不是0的话,那就是谎言
p[px] = py;
d[px] = d[y] - d[x];
p[px] = py表示把py作为px的父节点,这样的话,我们就不需要改动py的值,只需改动px的值就可以了
(d[x] - d[y] + d[px]) %3= 0 ==> d[px] = d[y] - d[x];
Java代码
import java.util.Scanner;
public class Main{
static int N = 50010;
static int[] p = new int[N]; //储存当前节点的父节点 一开始全指向自己
static int[] d = new int[N]; //储存当前节点到父节点的距离 一开始全是0
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
for(int i = 0; i < n; i ++) p[i] = i;
int res = 0;
while(k-- > 0){
int t = in.nextInt();
int x = in.nextInt();
int y = in.nextInt();
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 != 0) res ++;
else if(px != py)
{
p[px] = py;
d[px] = d[y] - d[x];
}
}
else if(t == 2)
{
if(px == py && (d[x] - d[y] - 1) % 3 != 0) res ++;
else if(px != py)
{
p[px] = py;
d[px] = d[y] - d[x] + 1;
}
}
}
}
System.out.print(res);
}
private static int find(int x)
{
if(x != p[x])
{
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
}