PKU Judge Online 1182 食物链

■1182 食物链

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code

package p1182;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    int INF=1<<28;
    double EPS=1e-9;

    int[] p;
    int[] rank;

    void run(){
        int n=Integer.parseInt(sc.next());
        int k=Integer.parseInt(sc.next());
        p=new int[3*n];
        rank=new int[3*n];
        for(int i=0; i<3*n; i++)
            p[i]=i;
        int ans=0;
        for(int i=0; i<k; i++){
            int d=Integer.parseInt(sc.next());
            int x=Integer.parseInt(sc.next())-1;
            int y=Integer.parseInt(sc.next())-1;
            if(x<0||x>=n||y<0||y>=n){
                ans++;
                continue;
            }
            if(d==1){
                // x=y
                if(same(x, y+n)||same(x, y+2*n)){
                    ans++;
                }else{
                    union(x, y);
                    union(x+n, y+n);
                    union(x+2*n, y+2*n);
                }
            }else if(d==2){
                // x->y
                // x=y+n
                if(same(x, y)||same(x, y+2*n)){
                    ans++;
                }else{
                    union(x, y+n);
                    union(x+n, y+2*n);
                    union(x+2*n, y);
                }
            }
        }
        println(""+ans);

    }

    boolean same(int x, int y){
        return findSet(x)==findSet(y);
    }

    void union(int x, int y){
        x=findSet(x);
        y=findSet(y);
        if(rank[x]<rank[y]){
            p[x]=y;
        }else{
            p[y]=x;
            if(rank[x]==rank[y])
                rank[x]++;
        }
    }

    int findSet(int x){
        if(p[x]!=x)
            p[x]=findSet(p[x]);
        return p[x];
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}