union find - Moonstone

union find – Moonstone

504 Words union find public class UnionFind { private List input; private Dictionary parent; public UnionFind(List input) { this.input = input; this.parent = new Dictionary(); foreach (int k in input) { this.parent.Add(k, k); } } public int Find(int a) { int p = parent[a]; while (p != a) { a = p; p = parent[a]; } return p; } public void Union(int a, int b) { int pa = Find(a); int pb = Find(b); if ((parent[pa] == pb) || (parent[pb] == pa)) { return; } parent[pa] = pb; } } public class UnionFind2 { private List input; private Dictionary parent; private Dictionary ranking; public UnionFind2(List input) { this.input = input; this.parent = new Dictionary(); this.ranking = new Dictionary(); foreach (var k in input) { this.parent.Add(k, k); this.ranking.Add(k, 0); } } public int Find(int k) { int p = parent[k]; while (p != k) { k = p; p = parent[k]; } return p; } public void Union(int a,

Read full article from union find – Moonstone