Last active
August 29, 2015 14:12
-
-
Save EmmanuelOga/bcafad14715a3f584e97 to your computer and use it in GitHub Desktop.
Non-Weighted UnionFind (disjoint set) implementation in Xtend (http://algs4.cs.princeton.edu/15uf/)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class UnionFind { | |
val int[] ids | |
var count = 0 | |
new(int size) { | |
count = size | |
ids = newIntArrayOfSize(size) | |
(0 ..< size).forEach[i|ids.set(i, i)] | |
} | |
def union(int p, int q) { | |
val idp = find(p) | |
val idq = find(q) | |
if (idp != idq) { | |
ids.set(idp, idq) | |
count-- | |
} | |
} | |
def find(int p) { | |
var c = p | |
while (c != ids.get(c)) { | |
c = ids.get(c) | |
} | |
c | |
} | |
def boolean connected(int p, int q) { | |
find(p) == find(q) | |
} | |
def count() { | |
count | |
} | |
def static void main(String[] args) { | |
val printer = [UnionFind it| ''' | |
independent nodes: «it.count» | |
0-1: «it.connected(0, 1)» 1-2: «it.connected(1, 2)» 0-9: «it.connected(0, 9)» | |
'''] | |
val uf = new UnionFind(10) | |
uf.union(0, 1) | |
println(printer.apply(uf)) | |
uf.union(1, 2) | |
println(printer.apply(uf)) | |
uf.union(2, 9) | |
println(printer.apply(uf)) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment