PKU Judge Online 1182 食物链

■1182 食物链

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

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

□Code

view plainprint?

1. package p1182;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7.   
8. import static java.lang.Math.*;  
9. import static java.util.Arrays.*;  
10.   
11. // AC  
12. public class Main{  
13.   
14.     Scanner sc=new Scanner(System.in);  
15.   
16.     int INF=1<<28;  
17.     double EPS=1e-9;  
18.   
19.     int[] p;  
20.     int[] rank;  
21.   
22.     void run(){  
23.         int n=Integer.parseInt(sc.next());  
24.         int k=Integer.parseInt(sc.next());  
25.         p=new int[3*n];  
26.         rank=new int[3*n];  
27.         for(int i=0; i<3*n; i++)  
28.             p[i]=i;  
29.         int ans=0;  
30.         for(int i=0; i<k; i++){  
31.             int d=Integer.parseInt(sc.next());  
32.             int x=Integer.parseInt(sc.next())-1;  
33.             int y=Integer.parseInt(sc.next())-1;  
34.             if(x<0||x>=n||y<0||y>=n){  
35.                 ans++;  
36.                 continue;  
37.             }  
38.             if(d==1){  
39.                 // x=y  
40.                 if(same(x, y+n)||same(x, y+2*n)){  
41.                     ans++;  
42.                 }else{  
43.                     union(x, y);  
44.                     union(x+n, y+n);  
45.                     union(x+2*n, y+2*n);  
46.                 }  
47.             }else if(d==2){  
48.                 // x->y  
49.                 // x=y+n  
50.                 if(same(x, y)||same(x, y+2*n)){  
51.                     ans++;  
52.                 }else{  
53.                     union(x, y+n);  
54.                     union(x+n, y+2*n);  
55.                     union(x+2*n, y);  
56.                 }  
57.             }  
58.         }  
59.         println(""+ans);  
60.   
61.     }  
62.   
63.     boolean same(int x, int y){  
64.         return findSet(x)==findSet(y);  
65.     }  
66.   
67.     void union(int x, int y){  
68.         x=findSet(x);  
69.         y=findSet(y);  
70.         if(rank[x]<rank[y]){  
71.             p[x]=y;  
72.         }else{  
73.             p[y]=x;  
74.             if(rank[x]==rank[y])  
75.                 rank[x]++;  
76.         }  
77.     }  
78.   
79.     int findSet(int x){  
80.         if(p[x]!=x)  
81.             p[x]=findSet(p[x]);  
82.         return p[x];  
83.     }  
84.   
85.     void print(String s){  
86.         System.out.print(s);  
87.     }  
88.   
89.     void println(String s){  
90.         System.out.println(s);  
91.     }  
92.   
93.     public static void main(String[] args){  
94.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
95.         new Main().run();  
96.     }  
97. }  

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();
    }
}