DSU Union Find

Run Settings
LanguageC#
Language Version
Run Command
using System; using System.Collections.Generic; using System.Linq; class MainClass { static void Main() { var list = new List<Device>(); list.Add(new Device() {Token1="a", Token2 = 3}); list.Add(new Device() {Token1="b", Token2 = 4}); list.Add(new Device() {Token1="a", Token2 = 6}); list.Add(new Device() {Token1="b", Token2 = 3}); list.Add(new Device() {Token1="c", Token2 = 4}); list.Add(new Device() {Token1="f", Token2 = 8}); list.Add(new Device() {Token1="g", Token2 = 6}); list.Add(new Device() {Token1="c", Token2 = 9}); list.Add(new Device() {Token1="k", Token2 = 12}); var count = GetUniqueDevices(list); Console.WriteLine(count); } public static int GetUniqueDevices(IList<Device> devices) { var dsu = new DSU(); // set up DSU foreach(var device in devices) { var hash = device.GetHash(); dsu.Parents.Add(hash, hash); } // O(n*n) for(int i = 0; i < devices.Count; i++) { for(int j = i + 1; j < devices.Count; j++) { if(devices[i].IsEqual(devices[j])) { dsu.Union(devices[i].GetHash(), devices[j].GetHash()); } } } int count = 0; foreach(var pair in dsu.Parents) { if(pair.Key == pair.Value) count++; } return count; } public class DSU { public Dictionary<string, string> Parents = new Dictionary<string, string>(); public DSU() { } public string FindParent(string x) { while(x != Parents[x]) { x = Parents[x]; } return x; } public void Union(string x, string y) { Parents[FindParent(y)] = FindParent(x); } } public class Device { public string Token1; public int Token2; public Device(){} public Device(string token1, int token2) { this.Token1 = token1; this.Token2 = token2; } public bool IsEqual(Device device) { if(this.Token1 == device.Token1 || this.Token2 == device.Token2) return true; return false; } public string GetHash() { return $"{Token1}|{Token2}"; } } }
Editor Settings
Theme
Key bindings
Full width
Lines