C#中合并嵌套列表中含共同元素的子列表至唯一列表

嘿，这个需求其实就是找连通分量——把所有有共享元素的子列表合并成一个，我给你两种实用的C#实现方案，看你的场景选：

方法一：并查集（Union-Find）解法 #

这种方法效率极高（时间复杂度接近O(n)），适合处理大规模的嵌套列表。核心思路是用一个字典追踪每个元素的“根节点”，把有关联的元素归到同一个根节点下，最后再按根节点分组。

using System;
using System.Collections.Generic;
using System.Linq;

public class ListMerger
{
    // 存储元素到其父节点的映射
    private Dictionary<int, int> _parentMap = new Dictionary<int, int>();

    // 查找元素的根节点，带路径压缩优化
    private int FindRoot(int element)
    {
        if (!_parentMap.ContainsKey(element))
            _parentMap[element] = element;
        
        if (_parentMap[element] != element)
            _parentMap[element] = FindRoot(_parentMap[element]);
        
        return _parentMap[element];
    }

    // 合并两个元素所在的集合
    private void MergeSets(int elementA, int elementB)
    {
        int rootA = FindRoot(elementA);
        int rootB = FindRoot(elementB);
        
        if (rootA != rootB)
            _parentMap[rootB] = rootA;
    }

    public List<List<int>> MergeConnectedLists(List<List<int>> inputLists)
    {
        // 第一步：遍历所有子列表，合并内部元素的集合
        foreach (var subList in inputLists)
        {
            if (subList.Count == 0) continue;
            
            int firstElement = subList[0];
            foreach (int num in subList.Skip(1))
            {
                MergeSets(firstElement, num);
            }
        }

        // 第二步：按根节点分组，用HashSet自动去重
        var groupedElements = new Dictionary<int, HashSet<int>>();
        foreach (var subList in inputLists)
        {
            foreach (int num in subList)
            {
                int root = FindRoot(num);
                if (!groupedElements.ContainsKey(root))
                    groupedElements[root] = new HashSet<int>();
                
                groupedElements[root].Add(num);
            }
        }

        // 第三步：转换为目标格式
        return groupedElements.Values.Select(set => set.ToList()).ToList();
    }
}

// 测试代码
public class Program
{
    public static void Main()
    {
        List<List<int>> myList = new List<List<int>>();
        myList.Add(new List<int> { 2, 7, 3 });
        myList.Add(new List<int> { 4, 6});
        myList.Add(new List<int> { 2, 5, 1 });
        myList.Add(new List<int> { 7, 0, 2 });
        myList.Add(new List<int> { 4, 9 });

        var merger = new ListMerger();
        var mergedResult = merger.MergeConnectedLists(myList);

        // 输出结果
        foreach (var list in mergedResult)
        {
            Console.WriteLine($"List<int> {string.Join(", ", list)}");
        }
        // 输出内容：
        // List<int> 2, 7, 3, 5, 1, 0
        // List<int> 4, 6, 9
    }
}

关键细节说明 #

• 路径压缩：FindRoot方法里的路径压缩能大幅减少后续查找的时间成本，避免树结构过深。
• HashSet去重：如果你的子列表里有重复元素，HashSet会自动帮你去重，最后转成List即可。

方法二：直观的集合合并法 #

如果你的嵌套列表规模不大，这种方法更易理解——维护一个结果集合列表，遍历每个子列表时，检查它和结果里的集合是否有交集，有就合并，没有就新增。

using System;
using System.Collections.Generic;
using System.Linq;

public class SimpleListMerger
{
    public List<List<int>> MergeConnectedLists(List<List<int>> inputLists)
    {
        var resultSets = new List<HashSet<int>>();

        foreach (var subList in inputLists)
        {
            var currentSet = new HashSet<int>(subList);
            // 找出所有和currentSet有交集的集合
            var overlappingSets = resultSets.Where(set => set.Overlaps(currentSet)).ToList();

            // 把重叠的集合合并到currentSet
            foreach (var set in overlappingSets)
            {
                foreach (int num in set)
                    currentSet.Add(num);
                resultSets.Remove(set);
            }

            resultSets.Add(currentSet);
        }

        // 转换为目标格式
        return resultSets.Select(set => set.ToList()).ToList();
    }
}

// 测试代码和方法一完全相同，输出结果一致

适用场景 #

这种方法代码更简洁，但时间复杂度是O(n²)，适合子列表数量少、元素不多的场景。

内容的提问来源于stack exchange，提问作者Martina