并查集例题

POJ 2236

很水的并查集题目，结构体中除了存坐标x,y以外还要存是否被维修过

合并的时候考虑的点比较多，假如当前修好的计算机编号是p，合并需要同时满足三个条件：1.合并的计算机编号不是p；2.合并的计算机与p的距离小于等于d；3.合并的计算机也是好的

import java.util.*;

public class Main {
    public static class Node {
        int x, y;
        boolean isGood;

        Node(int x, int y, boolean isGood) {
            this.x = x;
            this.y = y;
            this.isGood = isGood;
        }
    }

    public static class unionFindSet {
        public HashMap<Node, Node> fatherMap;
        public HashMap<Node, Integer> sizeMap;

        public unionFindSet() {
            fatherMap = new HashMap<Node, Node>();
            sizeMap = new HashMap<Node, Integer>();
        }

        public void makeSets(List<Node> nodes) {
            fatherMap.clear();
            sizeMap.clear();
            for (Node node : nodes) {
                fatherMap.put(node, node);
                sizeMap.put(node, 1);
            }
        }

        private Node findHead(Node node) {
            Node father = fatherMap.get(node);
            if (father != node)
                father = findHead(father);
            fatherMap.put(node, father);
            return father;
        }

        public boolean isSameSet(Node a, Node b) {
            return findHead(a) == findHead(b);
        }

        public void union(Node a, Node b) {
            if (a == null || b == null) {
                return;
            }
            Node aHead = findHead(a);
            Node bHead = findHead(b);
            if (aHead != bHead) {
                int aSetSize = sizeMap.get(aHead);
                int bSetSize = sizeMap.get(bHead);
                if (aSetSize <= bSetSize) {
                    fatherMap.put(aHead, bHead);
                    sizeMap.put(bHead, aSetSize + bSetSize);
                } else {
                    fatherMap.put(bHead, aHead);
                    sizeMap.put(aHead, aSetSize + bSetSize);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int d = cin.nextInt();
        unionFindSet ufd = new unionFindSet();
        List<Node> list = new LinkedList<Node>();
        for (int i = 0; i < n; i++) {
            int x = cin.nextInt();
            int y = cin.nextInt();
            list.add(new Node(x, y, false));
        }
        ufd.makeSets(list);
        while (cin.hasNext()) {
            String start = cin.next();
            if (start.equals("O")) {
                int p = cin.nextInt();
                Node a = list.get(p - 1);
                a.isGood = true;
                list.set(p - 1, a);
                for (int i = 0; i < list.size(); i++)
                    if (i != p - 1 && list.get(i).isGood && distance(a, list.get(i)) <= d * d)
                        ufd.union(a, list.get(i));
            } else if (start.equals("S")) {
                int p = cin.nextInt();
                int q = cin.nextInt();
                if (ufd.isSameSet(list.get(p - 1), list.get(q - 1)))
                    System.out.println("SUCCESS");
                else
                    System.out.println("FAIL");
            }
        }
    }

    static double distance(Node a, Node b) {
        return Math.pow((a.x - b.x), 2) + Math.pow((a.y - b.y), 2);
    }
}

POJ 1182

经典的种类并查集问题，我在这道题上卡了至少有一个星期才搞懂

比较简单的并查集开一倍空间存节点即可，但是这道题需要开三倍空间，我们把这三个空间分别记为A、B、C，对于任意一只动物，三个空间中都存有，比方说总共有N只动物，第i只动物的编号是i，那么在A、B、C三个空间中的编号分别为i、i + N、i + (N << 1)

这三个空间A、B、C之间相互有一定的关系，A中的所有动物吃B中的所有动物；B中的所有动物吃C中的所有动物；C中的所有动物吃A中的所有动物

在不考虑矛盾的情况下，合并同种动物a和b的代码如下

conn(a, b)
conn(a + N, b + N)
conn(a + (n << 1), b + (n << 1))

上面代码很好理解，就是将A空间内的a和b，以及B空间内的a和b；C空间内的a和b合并

由于三个空间具有相互捕食的关系，因此如果有动物a吃动物b，他们之间的合并代码应该如下所示

conn(a, b + N)
conn(a + N, b + (n << 1))
conn(a + (N << 1), b)

如果这里不理解，就回过头仔细看看A、B、C三个空间的关系

上面是不考虑矛盾的情况，实际上在所有的合并之前，应该考虑会不会存在矛盾，下面我们探讨如何判断矛盾

假设动物a和b是同一物种，那就去查询a和b + N、a和b + (N << 1)是否在同一个集合内，前者判断的是a是否吃b，后者判断的是b是否吃a，只要这两者满足其一，就和当前的操作矛盾（当前操作是a与b是同一物种）

假设a吃b，那就去查询a和b、a和b + (N << 1)是否在同一集合内，前者判断a和b是否是同一物种，后者判断b是否吃a（不可能存在a吃b，b也吃a），只要这两者满足其一，就和当前的操作矛盾（当前操作是a吃b）

#include <iostream>
using namespace std;
int n, m;
int f[150004];
int size[150004];
int find(int a) {
    if (f[a] == a)
        return a;
    return f[a] = find(f[a]);
}
bool same(int a, int b) {
    return find(a) == find(b);
} 
void conn(int a, int b) {
    int fa = find(a);
    int fb = find(b);
    if (fa != fb) {
        int sa = size[fa];
        int sb = size[fb];
        if (sa <= sb) {
            f[fa] = fb;
            size[fb] = sa + sb; 
        } else {
            f[fb] = fa;
            size[fa] = sa + sb;
        }
    }
} 
int main() {
    int ans = 0;
    scanf("%d %d", &n, &m);
    for (int i = 0; i <= (n << 1) + n; i++) {
        f[i] = i; 
        size[i] = 1;
    }
    for (int i = 0; i < m; i++) {
        int op, a, b;
        scanf("%d %d %d", &op, &a, &b);
        if (a > n || b > n || a < 1 || b < 1)
            ans++;
        else if (op == 2 && a == b)
            ans++;
        else if (op == 1) {
            if (same(a, b + n) || same(a, b + (n << 1)))
                ans++;
            else {
                conn(a, b);
                conn(a + n, b + n);
                conn(a + (n << 1), b + (n << 1));
            }
        } else {
            if (same(a, b) || same(a, b + (n << 1)))
                ans++;
            else {
                conn(a, b + n);
                conn(a + n, b + (n << 1));
                conn(a + (n << 1), b);
            }
        }
    }
    printf("%d\n",ans);
}