Poj Solution 1182

http://poj.org/problem?id=1182

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Main poj = new Main();

        BufferedReader read = new BufferedReader(new InputStreamReader(
                System.in));
        String[] tm = read.readLine().split(" ");

        int N = new Integer(tm[0]);
        int K = new Integer(tm[1]);
        poj.initial(N);
        int i = 0;
        int count = 0;
        if (K == 0)
            System.out.println(count);
        while (++i <= K) {
            String[] tmp = read.readLine().split(" ");
            int kind = new Integer(tmp[0]);
            int animalA = new Integer(tmp[1]);
            int animalB = new Integer(tmp[2]);

            if (animalA > N || animalB > N) {
                count++;
                continue;
            }
            if (animalA == animalB) {
                if (kind == 2)
                    count++;
                continue;
            }
            int fa = poj.find(animalA);
            int fb = poj.find(animalB);

            if (fa == fb) {
                if (kind == 1) {
                    if (poj.mod[animalA] != poj.mod[animalB])
                        count++;
                } else {
                    if ((poj.mod[animalA] + 1) % 3 != poj.mod[animalB] % 3)
                        count++;
                }
            } else
                poj.union(animalA, animalB, kind);
        }
        read.close();
        System.out.println(count);
    }

    int[] parent;
    int[] mod;

    void union(int x, int y, int kind) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            if (mod[x] < mod[y]) {
                parent[fx] = fy;
                if (kind == 2)
                    mod[fx] = (mod[y] - mod[x] - 1 + 3) % 3;
                else
                    mod[fx] = (mod[y] - mod[x]) % 3;
            } else {
                parent[fy] = fx;
                if (kind == 2)
                    mod[fy] = (mod[x] - mod[y] + 1) % 3;
                else
                    mod[fy] = (mod[x] - mod[y]) % 3;
            }
        }

    }

    int find(int x) {
        if (x == parent[x])
            return parent[x];
        else {
            int t = parent[x];
            parent[x] = find(parent[x]);
            mod[x] = (mod[x] + mod[t]) % 3;
        }
        return parent[x];
    }

    void initial(int n) {
        parent = new int[n + 1];
        mod = new int[n + 1];
        for (int i = 1; i < n + 1; i++)
            parent[i] = i;
    }
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *