AcWing 240. 食物链-java-带简单注释
原题链接
中等
作者:
Astarion
,
2021-02-05 22:12:35
,
所有人可见
,
阅读 316
import java.io.*;
class Main {
static final int N = 50010;
static int[] p = new int[N];
static int[] d = new int[N];
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) throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader in = new BufferedReader(isr);
String[] strs = in.readLine().split(" ");
int n = Integer.parseInt(strs[0]);
int k = Integer.parseInt(strs[1]);
//初始化P数组
for (int i = 1; i<=n; i++) p[i] = i;
int ans = 0;
for (int i = 0; i<k; i++) {
strs = in.readLine().split(" ");
int op = Integer.parseInt(strs[0]);
int x = Integer.parseInt(strs[1]);
int y = Integer.parseInt(strs[2]);
if (x>n || y>n) {ans++;continue;}
int px = find(x);
int py = find(y);
switch (op) {
case 1 : {
//同一个集合中,表示已确立相互关系
if (px == py) {
if ((d[x] - d[y])%3 != 0) {
ans++;
continue;
}
}
//不同集合中,现在建立相互关系
else {
d[px] = d[y] - d[x];
p[px] = py;
}
break;
}
case 2 : {
//同一个集合中,表示已确立相互关系
if (px == py) {
//推导出的关系为 (d[x]-d[y])%3 == 1 则认为x可以吃y
//写成(d[x]-d[y]-1)%3 == 0 可以避免余数是负数的问题
//也可以写成(d[x]-d[y])%3 +3 == 1
//==正确 -> != 错误
if ((d[x] - d[y] - 1) % 3 != 0) {
ans++;
continue;
}
}
//不同集合中,现在建立相互关系
else {
d[px] = d[y] - d[x] + 1;
p[px] = py;
}
break;
}
default : System.out.print("--");
}
}
System.out.println(ans);
//System.out.print((-2)%3 + 3);
}
}