并查集例题

关于并查集的介绍可以看我之前的文章并查集 Union Find

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

POJ 1703展开目录

题目大意是说，有两类团伙，输入 D a b 表示确认 a 和 b 是不同的团伙，输入 A a b 表示查询 a 和 b 是否是同一团伙

和食物链相比这算是比较简单的种类并查集，问题在于如何处理不同的关系，并查集维护的是相同的集合，但这道题维护的是不同的

具体做法是开两倍空间 A 和 B，第 i 个人在 A 和 B 空间的编号分别为 i,i + N。conn (a, b) 表示 a 和 b 属于同一集合，conn (a, b + n) 和 conn (a + n, b) 表示 a 和 b 属于不同集合

如果 a 和 b 是同伙，则 same (a, b) 或 same (a + n, b + n) 返回 true

如果 a 和 b 不是同伙，则 same (a, b + n) 或 same (a + n, b) 返回 true

如果上面两种情况都没有，说明这两个人暂时不知道什么关系

#include <iostream>
using namespace std;
int n, m;
int f[200005];
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)
        f[fa] = fb;
}
int main() {
    int ans = 0;
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        for (int i = 0; i <= (n << 1); i++)
            f[i] = i;
        for (int i = 0; i < m; i++) {
            char op;
            int a, b;
            scanf("\n%c%d%d", &op, &a, &b);
            if (op == 'D') {
                conn(a, b + n);
                conn(a + n, b);
            } else {
                if (same(a, b + n) || same(a + n, b))
                    printf("In different gangs.\n");
                else if (same(a, b) || same(a + n, b + n))
                    printf("In the same gang.\n");
                else
                    printf("Not sure yet.\n");
            }
        }
    }
    return 0;
}

AOJ 2170展开目录

这题目我看了半天实在是看不太懂，最后找谷歌翻译了全篇

大意是说输入 N 个点，Q 次操作。接下来输入 N-1 行数据，第一行输入 p1 表示第 2 个点的父节点是 p1，第二行输入 p2 表示第 3 个点的父节点是 p2。然后输入 Q-1 行操作，M a 表示标记 a 点，Q b 表示询问离 b 最近的被标记的祖先

水题，标记这个操作其实可以看作将节点的父节点指向自己，即将当前节点从其父节点中分离出来，但是跟在当前节点后面的所有节点还是跟着自己

为了保证节点间的关系，不能使用路径压缩

#include <stdio.h>
#define ll long long
int f[100001];
int find(int a) {
    return a == f[a] ? a : find(f[a]);
}
int main() {
    ll n, m;
    while (scanf("%lld %lld", &n, &m) != EOF && n + m) {
        for (int i = 2; i <= n; i++)
            scanf("%d", &f[i]);
        f[1] = 1;
        ll ans = 0;
        char op[5];
        int t;
        for (int i = 0; i < m; i++) {
            scanf("%s%d",op, &t);
            if (op[0] == 'Q')
                ans += find(t);
            else
                f[t] = t;
        }
        printf("%lld\n", ans);
    }
    return 0;
}