[Swift]经典解题思路:联合查找Union Find

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/ ）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10414498.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

详情点击：[Swift]LeetCode547. 朋友圈 | Friend Circles

【结构】

 1 public struct UnionFind<T: Hashable> {
 2     private var index: [T: Int] = [:]
 3     private var parent: [Int] = []
 4     private var size: [Int] = []
 5     public var numerOfSets: Int = 0 
 6     
 7     public mutating func addSet(_ element: T) {
 8         if index[element] == nil {
 9             index[element] = parent.count
10             parent.append(parent.count)
11             size.append(1)
12             numerOfSets += 1
13         }
14     }
15     
16     public mutating func find(_ element: T) ->Int? {
17         guard let index = index[element] else {
18             return nil 
19         }
20         return setByIndex(index)
21     }
22     
23     private mutating func setByIndex(_ index: Int) -> Int {
24         if parent[index] == index {
25             return index 
26         } else {
27             parent[index] = setByIndex(parent[index])
28             return parent[index]
29         }
30     }
31     
32     public mutating func union(_ element1: T, _ element2: T) {
33         guard let set1 = find(element1), let set2 = find(element2) else {
34             return 
35         }
36         
37         if set1 != set2 {
38             numerOfSets -= 1 
39             if size[set1] > size[set2] {
40                 parent[set2] = set1 
41                 size[set1] += size[set2]
42             } else {
43                 parent[set1] = set2 
44                 size[set2] += size[set1]
45             }
46         }
47     }
48 }

【类】

 1 class UnionFind {
 2     private var connectivities: [Int]
 3     private var sizes: [Int]
 4     init(size: Int) {
 5         self.connectivities = [Int](repeating: 0, count: size)
 6         self.sizes = [Int](repeating: 1, count: size)
 7         for i in 0..<size {
 8             connectivities[i] = i
 9         }
10     }
11     func connect(n1: Int, n2: Int) {
12         guard let root1 = root(of: n1),
13             let root2 = root(of: n2),
14             root1 != root2 else { return }
15         let sz1 = sizes[root1]
16         let sz2 = sizes[root2]
17         if sz1 > sz2 {
18             connectivities[root2] = root1
19             sizes[root1] += sizes[root2]
20         } else {
21             connectivities[root1] = root2
22             sizes[root2] += sizes[root1]
23         }
24     }
25     func isConnected(n1: Int, n2: Int) -> Bool {
26         return root(of: n1) == root(of: n2)
27     }
28     func root(of n: Int) -> Int? {
29         guard n < connectivities.count else { return nil }
30         let parent = connectivities[n]
31         if parent == n {
32             return n
33         }
34         guard let rt = root(of: parent) else { return nil }
35         connectivities[n] = rt
36         return rt
37     }
38     func snapshot() {
39         print("c: (connectivities)")
40         print("s: (sizes)")
41     }
42 }