[Swift]DJSet
发布时间:2020-12-14 05:09:27 所属栏目:百科 来源:网络整理
导读: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
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 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |