首页 > 专题系列 > Java解POJ > POJ 1182 食物链 [解题报告] Java
2013
11-09

POJ 1182 食物链 [解题报告] Java

食物链

问题描述 :

动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。

现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。

有人用两种说法对这N个动物所构成的食物链关系进行描述:

第一种说法是”1 X Y”,表示X和Y是同类。

第二种说法是”2 X Y”,表示X吃Y。

此人对N个动物,用上述两种说法,一句接一句地说出K句话,这K句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。

1) 当前的话与前面的某些真的话冲突,就是假话;

2) 当前的话中X或Y比N大,就是假话;

3) 当前的话表示X吃X,就是假话。

你的任务是根据给定的N(1 <= N <= 50,000)和K句话(0 <= K <= 100,000),输出假话的总数。

输入:

第一行是两个整数N和K,以一个空格分隔。

以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。

若D=1,则表示X和Y是同类。

若D=2,则表示X吃Y。

输出:

只有一个整数,表示假话的数目。

样例输入:

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

样例输出:

3

解题代码:

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