并查集模板:食物链详解

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;public class Main {static int N = 50010;static int n,m; //n个动物,m局判断static int[] p = new int[N];    //p[i]是i的根节点static int[] d = new int[N];    //d[i]表示i到其父节点的距离,通过find函数会路径压缩变成到根节点的具体static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));public static int find(int x){  //返回根节点if (p[x] != x){ //如果你要找的节点不仅仅只有自己,就要往上找,去找自己的祖宗//先递归得到根节点//假设此时已经形成了一段树,p[x] = N,从p[1]开始找,一直让x增到N即p[N] = N;int t = find(p[x]);//调用结束的x是 根节点N - 1,根节点的d[N]不需要更新//从根节点开始的孩子开始,回溯,路径压缩更新该节点到根节点的距离//再调用find方法前,会设置d[p[x]]为1d[x] += d[p[x]];p[x] = t;   //最后再更新find(x)~find(N-1)的父节点为N}//最后返回根节点Nreturn p[x];}public static void main(String[] args) throws IOException {String[] init = in.readLine().split(" ");n = Integer.parseInt(init[0]);m = Integer.parseInt(init[1]);//初始化并查集for (int i = 0; i < n; i++) {p[i] = i;}int res = 0;    //说谎话的个数while (m-- > 0){init = in.readLine().split(" ");int t= Integer.parseInt(init[0]);int x= Integer.parseInt(init[1]);int y= Integer.parseInt(init[2]);if (x > n || y > n) res ++;else {int px = find(x),py = find(y);  //找到这两个树的根节点if (t == 1)//同类{//作为同类如果再一个集合关系里,他们的等级相差%3！= 0if (px == py &&  (d[x] - d[y]) % 3 != 0) res ++;else if (px != py){ //这里要用else if 不能直接用else，同类也可能走到这//不同类,把它俩放在一个集合里p[px] = py; //py作为px的父亲d[px] = (d[y] - d[x]) % 3;}}else {//吃,如果在一个集合里,同类的化,x 吃 y//x在%3的情况下要比y多一个等级if (px == py && (d[x] - d[y] - 1) % 3 != 0) res ++;else if (px != py){//不同一个集合,把他们放在一起,x比y高一个等级p[px] = p[y];//在调用find之前会先走这里,把根节点的到它的孩子距离设置成1d[px] = (d[y] - d[x] + 1) % 3;}}}}System.out.println(res);}
}