Skip to content

Instantly share code, notes, and snippets.

@n1ghtmare
Last active August 29, 2015 14:03
Show Gist options
  • Save n1ghtmare/7af82239365f9e9eb927 to your computer and use it in GitHub Desktop.
Save n1ghtmare/7af82239365f9e9eb927 to your computer and use it in GitHub Desktop.
UnionFind in Swift
class UnionFind {
var id:Int[];
var count:Int;
init(N:Int) {
count = N;
id = [];
for(var i = 0; i < N; i++) {
id.append(i);
}
}
func find(p:Int) -> Int {
return id[p];
}
func connected(p:Int, q:Int) -> Bool {
return find(p) == find(q);
}
func union(p:Int, q:Int) {
var pId = find(p);
var qId = find(q);
if(pId != qId) {
return;
}
for i in 0..id.count {
if(id[i] == pId) {
id[i] = qId;
}
count--;
}
}
}
var uf = UnionFind(N: 100);
uf.connected(10, q:11);
uf.union(10, q: 11);
uf.connected(10, q: 11);
uf.union(11, q: 53);
uf.connected(10, q: 53);
uf.union(10, q: 54);
uf.connected(53, q: 54);
uf.connected(11, q: 54);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment