Create combined Lists from multiple Lists

Question

I can't quite get my head around trying to figure this out but I'll explain as follows,

var combinedCoords = new List<List<int>>();

var coords = new List<List<int>>
{
    new List<int>() {0, 1},
    new List<int>() {0, 1, 2},
    new List<int>() {1, 3, 4, 5},
    new List<int>() {3, 4},
    new List<int>() {7, 8},
    new List<int>() {7, 8, 9},
    new List<int>() {8, 9, 10}
};

Here I have the var coords which contains some List<int>; what I need is for some new lists to be populated inside combinedCoords which will contain some combined lists where there are numbers in common. From this there should be 2 combined lists produced, the first will be {0,1,2,3,4,5} and the second will be {7,8,9,10}. To further illustrate what I'm trying to say, below is a graphical representation were each circle is a list; the red number in brackets denotes the index of each list.

_{(source: aboutireland.ie)}

Answer 1

It looks like what you're looking for is a connected component list. I answered a similar question about this here, but this question is different enough that I think it warrants it's own answer:

var combinedCoords = new List<List<int>>();
foreach(var c in coords)
{
    var merge = new List<List<int>>();
    foreach(var g in combinedCoords)
    {
        if (c.Any(g.Contains))
        {
            merge.Add(g);
        }
    }

    if (merge.Count == 0)
    {
        combinedCoords.Add(c);
    }

    merge.Add(c);
    for(int i = 1; i < merge.Count; i ++)
    {
        foreach(var v in merge[i].Except(merge[0]))
        {
            merge[0].Add(v);
        }

        combinedCoords.Remove(merge[i]);
    }
}

This produces two lists:

{ 0, 1, 2, 3, 4, 5 }
{ 7, 8, 9, 10 }

If you refactor coords and combinedCoords to be a List<HashSet<int>>, the algorithm is a little simpler, and it should perform better:

var combinedCoords = new List<HashSet<int>>();
foreach(var c in coords)
{
    var merge = new List<HashSet<int>>(combinedCoords.Where(c.Overlaps));
    if (merge.Count == 0)
    {
        combinedCoords.Add(c);
    }
    else
    {
        merge[0].UnionWith(c);
        for(int i = 1; i < merge.Count; i ++)
        {
            merge[0].UnionWith(merge[i]);
            combinedCoords.Remove(merge[i]);
        }
    }
}