Java实现 洛谷 P2024 [NOI2001]食物链

输入输出样例
输入 #1

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

输出 #1

3

 
import java.util.Scanner;public class Main {static int x[],sum=0;
public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();x=new int[n*4];//储存祖宗,储存每个对象以及天敌,所捕食动物for (int i = 0; i < x.length; i++) {x[i]=i;}TO:for (int i = 0; i <m; i++) {int a=sc.nextInt();int b=sc.nextInt();int c=sc.nextInt();if(c>n||b>n){sum++;continue TO;}if(a==2){if(c==b){sum++;continue TO;}}if(a==1){if(find(b+n)==find(c)||find(b+2*n)==find(c)){sum++;continue TO;}else{contic(b,c);contic(b+n,c+n);contic(b+2*n,c+2*n);}}if(a==2){if(find(b)==find(c)||find(b+2*n)==find(c)){sum++;continue TO;}else{contic(b+n,c);contic(b+2*n,c+n);contic(c+2*n,b);}}}System.out.println(sum);}
public static int find(int p){return x[p]==p?p:find(x[p]);
}
public static void contic(int q,int p){int Q=find(q);int P=find(p);if(Q==P){return;}x[Q]=P;}
}