DSU Union Find
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106
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}";
}
}
}
Csharp
INFO