Created
October 27, 2020 19:19
-
-
Save MaxWellHays/d11863a8c412c3f27659d964d013f8ba to your computer and use it in GitHub Desktop.
C# DisjointSet implementation (UnionFind)
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
using System.Collections.Generic; | |
public class DisjointSet<T> | |
{ | |
Dictionary<T, T> parents = new Dictionary<T, T>(); | |
Dictionary<T, int> weights = new Dictionary<T, int>(); | |
public T Union(T a, T b) { | |
var aParent = Find(a); | |
var bParent = Find(b); | |
if (weights[aParent] >= weights[bParent]) { | |
parents[bParent] = aParent; | |
return aParent; | |
} | |
else { | |
parents[aParent] = bParent; | |
return bParent; | |
} | |
} | |
public T Find(T child, bool createIfNotExist = true, bool compressPaths = true) | |
{ | |
if (parents.TryGetValue(child, out var parent)) { | |
if (!child.Equals(parent)) { | |
parent = Find(parent, createIfNotExist, compressPaths); | |
if (compressPaths) { | |
var oldParent = parents[child]; | |
weights[oldParent]--; | |
parents[child] = parent; | |
weights[parent]++; | |
} | |
} | |
return parent; | |
} | |
if (createIfNotExist) { | |
parents[child] = child; | |
weights[child] = 0; | |
} | |
return child; | |
} | |
public IEnumerable<T> GetRootValues() { | |
foreach (var kvp in parents) | |
{ | |
if (kvp.Key.Equals(kvp.Value)) { | |
yield return kvp.Key; | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment