刷题笔记27——并查集

很长一段时间，我的生活看似马上就要开始了。但是总有一些障碍阻挡着，有些事得先解决，有些工作还有待完成，时间貌似不够用，还有一笔债务8要去付清，然后生活就会开始。最后我终于明白，这些障碍，正是我的生活。 ——艾弗里德·德索萨

990. 等式方程的可满足性（一个比较经典的并查集例子）

class Solution {
    public boolean equationsPossible(String[] equations) {
        UF uf = new UF(26);
        for(String eq:equations){
            if(eq.charAt(1) == '='){
                char x = eq.charAt(0);
                char y = eq.charAt(3);
                uf.union(x-'a',y-'a');
            }
        }

        for(String eq:equations){
            if(eq.charAt(1) == '!'){
                char x = eq.charAt(0);
                char y = eq.charAt(3);
                if(uf.connocted(x-'a',y-'a')){
                    return false;
                }
            }
        }
        return true;
    }  
}

class UF{
    private int count;
    private int[] parent;

    public UF(int n){
        this.count = n;
        parent = new int[n];
        for(int i=0;i<n;i++){
            parent[i] = i;
        }
    }

    public void union(int p,int q){
        int rootP = find(p);
        int rootQ = find(q);

        if(rootP == rootQ) return;

        parent[rootP] = rootQ;
        count--;
    }

    public boolean connocted(int p,int q){
        int rootP = find(p);
        int rootQ = find(q);
        return rootP==rootQ;
    }

    public int find(int p){
        if(p!= parent[p]){
            parent[p] = find(parent[p]);
        }
        return parent[p];
    }

    public int count(){
        return count;
    }


}
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

后续再补充真题