并查集

发表于 | 分类于

并查集 union-find

并查集其实就是构建一个森林，对有公共父节点的多叉树合并。
问题：假如有1-10个人，互相认识的人构成一个朋友圈，两个朋友圈中没有相互认识的两个人，问能够构成几个盆友圈。

solution

开一个size数组，下标代表每个人所认识的人数，parent数组下标代表自己的父节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
public class unionFind {
    public static int solution (List<List<Integer>> list) {
        int[] size = new int[10];
        int[] parent = new int[10];
        for (int i = 0; i < size.length; i++) {
            size[i] = 0;
            parent[i] = i;
        }
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).size() != 0) {
                Set<Integer> set = new HashSet<>();
                if (parent[i] != i)
                    set.add(parent[i]);
                for (Integer t : list.get(i)) {
                    int root = find(t, parent);
                    if (root != t) {
                        set.add(root);
                        continue;
                    }
                    if (parent[i] != t) {
                        parent[t] = i;
                        size[i]++;
                        size[t]--;
                    }
                }
                for (Integer t : set) {
                    union(t, i, size, parent);
                }
            }
        }
        for (int i = 0; i < parent.length; i++) {
            if (parent[i] != find(i, parent)) {
                size[i] += size[parent[i]];
                size[parent[i]] = -1;
                parent[i] = find(i, parent);
            }
        }
        int count = 0;
        for (int i = 0; i < size.length; i++)
            if (size[i] >= 0)
                count++;
        return count;
    }

    //寻找自己的根节点
    private static int find (int x, int[] parent) {
        if (parent[x] == x)
            return x;
        else
            return find(parent[x], parent);
    }

    //合并有相同父节点的两棵树
    private static void union (int l, int r, int[] size, int[] parent) {
        int xparent = find(l, parent);
        int yparent = find(r, parent);
        if (xparent == yparent)
            return;
        for (int i = 0; i < parent.length; i++) {
            if (find(i, parent) == yparent) {
                parent[i] = xparent;
                size[xparent]++;
                size[yparent]--;
            }
        }
    }

}
Thanks!