题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

Java 代码

import java.util.Scanner; //n 同类 n+n 捕食 n+n+n 天敌
public class Main{
    static int N=200010,n,m;
    static int p[]=new int[N];
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        for(int i=1;i<=n*3;i++) p[i]=i;
        int res=0;
        while(m--!=0){
            int a=sc.nextInt();
            int b=sc.nextInt();
            int c=sc.nextInt();
            if(b>n||c>n) res++;
            else if(a==1){
                if(find(b+n)==find(c)||find(b+n+n)==find(c)) res++;
                else{
                  unin(b,c);unin(b+n,c+n);unin(b+n+n,c+n+n);  
                }
            }else{
                if(b==c||find(b)==find(c)||find(b)==find(c+n)) res++;
                else{
                    unin(b+n,c);
                    unin(b+n+n,c+n);
                    unin(b,c+n+n);
                }
            }
        }
        System.out.println(res);
    }
    static int find(int x){
        if(x!=p[x]){
            p[x]=find(p[x]);
        }
        return p[x];
    }
    static void unin(int x,int y){
        int xx=find(x),yy=find(y);
        p[xx]=yy;
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla