★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/ ）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10053038.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
1 public class DJSet 2 { 3 var upper:[Int] 4 var w:[Int] 5 6 init(_ n:Int) 7 { 8 upper = [Int](repeating:-1,count:n) 9 w = [Int](repeating:0,count:n) 10 } 11 12 func root(_ x:Int) -> Int 13 { 14 if(upper[x] < 0) 15 { 16 return x 17 } 18 else 19 { 20 upper[x] = root(upper[x]) 21 return upper[x] 22 } 23 } 24 25 func equiv(_ x:Int,_ y:Int) -> Bool 26 { 27 return root(x) == root(y) 28 } 29 30 func union(_ x:Int,_ y:Int) -> Bool 31 { 32 var x:Int = root(x) 33 var y:Int = root(y) 34 if x != y 35 { 36 if upper[y] < upper[x] 37 { 38 var d:Int = x 39 x = y 40 y = d 41 } 42 upper[x] += upper[y] 43 upper[y] = x 44 w[x] += w[y] 45 } 46 return x == y 47 } 48 49 func count() -> Int 50 { 51 var ct:Int = 0 52 for u in upper 53 { 54 if u < 0 55 { 56 ct += 1 57 } 58 } 59 return ct 60 } 61 }