MENU

并查集例题

January 11, 2019 • Read: 670 • 算法

关于并查集的介绍可以看我之前的文章并查集 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;
} 
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment