首页

并查集算法模板

1971. 寻找图中是否存在路径 - 力扣（LeetCode）

684. 冗余连接 - 力扣（LeetCode）

685. 冗余连接 II - 力扣（LeetCode）

685. 冗余连接 II - 力扣（LeetCode）

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
class UnionSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n

        def isSame(self, u, v):
            u = self.find(u)
            v = self.find(v)
            return u == v

        def find(self, u):
            if u == self.parent[u]:
                return u
            else:
                self.parent[u] = self.find(self.parent[u])
                return self.parent[u]

        def union(self, u, v):
            u = self.find(u)
            v = self.find(v)
            if u == v:
                return
            # if self.rank[u] <= self.rank[v]:
            #     self.parent[u] = v
            #     if self.rank[u] == self.rank[v]:
            #         self.rank[v] += 1
            # else:
            #	  self.parent[v] = u
            self.parent[v] = u
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
class UnionSet{
    int[] parent;
    int[] rank;

    public UnionSet(int n){
        parent = new int[n];
        rank = new int[n];
        for(int i = 0; i < n; ++i){
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int u){
        return u == parent[u]? u:(parent[u] = find(parent[u]));
    }

    public void union(int u, int v){
        u = find(u);
        v = find(v);
        if(u != v){
            if(rank[u] <= rank[v]){
                parent[u] = v;
                if(rank[u] == rank[v]){
                    rank[v]++;
                }
            }else{
                parent[v] = u;
            }
            // parent[u] = v;
        }
    }

    public boolean isSame(int u, int v){
        return find(u) == find(v);
    }
}
更新于 阅读次数 次