Skip to content

Instantly share code, notes, and snippets.

@MaxWellHays
Created October 27, 2020 19:19
Show Gist options
  • Save MaxWellHays/d11863a8c412c3f27659d964d013f8ba to your computer and use it in GitHub Desktop.
Save MaxWellHays/d11863a8c412c3f27659d964d013f8ba to your computer and use it in GitHub Desktop.
C# DisjointSet implementation (UnionFind)
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