查找链接元素

Question

再会！ 我有一个字典 Dictionary> 其中 List 的值可以是字典的键。

我想要做的是分离这个字典的键和值来设置表示链接元素。因此，如果我有，

dict[1] = new List<long>() { 12, 4, 2 };
dict[2] = new List<long>() { 7 };
dict[3] = new List<long>() { 25, 19, 27 };

我想得到两个集合 { 1, 12, 4, 2, 7 } 和 { 3, 25, 19 27 } 作为输出；

我找到了一个解决方案，但它看起来不够快。

 List<HashSet<long>> graphs = new List<HashSet<long>>();
 foreach (var kv in dict)
 {
     HashSet<long> maybeNewGraph = new HashSet<long>(kv.Value);
     maybeNewGraph.Add(kv.Key);

     bool success = false;
     foreach (var hashSet in graphs)
     {
        if (hashSet.Overlaps(maybeNewGraph))
        {
            hashSet.UnionWith(maybeNewGraph);
            success = true;
            break;
        }
     }
     if (!success)
     {
        graphs.Add(maybeNewGraph);
     }
 }

对于这样的问题有更好的解决方案吗？ 谢谢。

UPD：更正示例。谢谢斯维克

Answer 1

在我看来，您正在尝试实现一种算法来解决不相交集。幸运的是，网络上有现有技术。现在我已经向您提供了正确的搜索词，维基百科是一个很好的起点。

这是一个 c# 实现。我不能保证它的效率。