Finding linked elements

Question

Good day! I have a dictionary Dictionary<long, List<long>> where values of List can be keys of dictionary.

What I want to do is to separate keys and values of this dictionary to set that represent linked elements. So if i have

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

I want to get as output tow sets { 1, 12, 4, 2, 7 } and { 3, 25, 19 27 };

I found a solution but it looks for me that it is not fast enough.

 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);
     }
 }

Are there better solutions for such a problem? Thank you.

UPD : corrected exmaple. Thanks svick

Answer 1

Looks to me like you're trying to implement an algorithm for solving disjoint sets. Luckily for you, there's prior art on the web. Now I've handed you the correct search term, Wikipedia is a good place to start.

Here's a c# implementation. I can't vouch for its efficiency.