Device Union BFS
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 set = new Dictionary<string, Device>();
var graph = new Dictionary<string, HashSet<string>>();
for(int i = 0; i < devices.Count; i++)
{
set.Add(devices[i].GetHash(), devices[i]);
for(int j = i + 1; j < devices.Count; j++)
{
if(!devices[i].IsEqual(devices[j]))
continue;
// build graph
if(graph.ContainsKey(devices[i].GetHash()))
graph[devices[i].GetHash()].Add(devices[j].GetHash());
else graph.Add(devices[i].GetHash(), new HashSet<string>(){ devices[j].GetHash() });
if(graph.ContainsKey(devices[j].GetHash()))
graph[devices[j].GetHash()].Add(devices[i].GetHash());
else graph.Add(devices[j].GetHash(), new HashSet<string>(){ devices[i].GetHash() });
}
}
int count = 0;
var queue = new Queue<string>();
while(set.Count > 0)
{
queue.Enqueue(set.First().Key);
var visited = new HashSet<string>();
while(queue.Count > 0)
{
var loop = queue.Count;
for(int i = 0; i < loop; i++)
{
var hash = queue.Dequeue();
visited.Add(hash);
set.Remove(hash);
if(graph.ContainsKey(hash))
foreach(var child in graph[hash])
{
if(!visited.Contains(child))
queue.Enqueue(child);
}
}
}
count++;
}
return count;
}
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