AcWing 240. 食物链(JAVA)
原题链接
中等
作者:
鼠鼠我
,
2021-02-01 21:55:42
,
所有人可见
,
阅读 337
import java.util.Scanner;
public class Main {
static int M = 500010;
static int d[] = new int[M];//结点到父节点的距离!!!
static int p[] = new int[M];//p[i]代表i的祖宗结点
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
for (int i = 1; i <=n; i ++ ) p[i] = i;
int res = 0;
while(m-- >0)
{
int t = sc.nextInt();
int x = sc.nextInt();
int y = sc.nextInt();
if(x>n || y>n) res ++;
else
{
int px = find(x);
int py = find(y);
if(t==1)//看是否x和y是同类
{
if(px==py && (d[x]-d[y])%3!=0) //如果x和y的根节点相同且到根节点的距离之差模3==0
res++;
else if(px!=py)//如果根节点不同
{
p[px] = py;//把y的根节点赋值给px的根节点
d[px] = d[y] - d[x];//更新px到根节点的距离
}
}
else
{
if(px==py && (d[x]-d[y]-1)%3!=0) //如果x和y的根节点相同且到根节点的距离之差模3==1
res++;
else if(px!=py)
{
p[px] = py;//把y的根节点赋值到px的根节点
d[px] = d[y] + 1 - d[x];//更新px到根节点的距离
}
}
}
}
System.out.println(res);
}
static int find(int x)
{
if(p[x]!=x)
{
int t = find(p[x]);//先把x的根节点赋值给t
d[x] += d[p[x]];//x到根节点的距离等于x到父节点的距离加父节点到根节点的距离
p[x] = t;//把t赋值给p[x];
}
return p[x];
}
}