如何实现关联Tuple<int, int>数对的分组合并操作？

你定义了一个Tuple<int, int>类型的列表：

List<Tuple<int, int>> pairs = new List<Tuple<int, int>>();

并添加了以下数对：

• pairs.Add(Tuple.Create<int, int>(1, 2));
• pairs.Add(Tuple.Create<int, int>(3, 4));
• pairs.Add(Tuple.Create<int, int>(3, 5));
• pairs.Add(Tuple.Create<int, int>(5, 6));
• pairs.Add(Tuple.Create<int, int>(10, 11));
• pairs.Add(Tuple.Create<int, int>(2, 3));

你希望将这些数对按关联性分组合并，最终得到：

• result[0] = {1, 2, 3, 4, 5, 6}
• result[1] = {10, 11}

请问是否有简便的实现方法？

这是处理这类“关联元素合并”问题最高效且简洁的方案，核心思路是用一个轻量数据结构跟踪每个元素的父节点，快速判断两个元素是否属于同一集合，并完成集合合并，完美匹配你要的分步关联逻辑。

第一步：实现并查集工具类 #

public class UnionFind
{
    private Dictionary<int, int> _parent;

    public UnionFind()
    {
        _parent = new Dictionary<int, int>();
    }

    // 查找元素的根节点，附带路径压缩优化（让后续查找更快）
    public int Find(int x)
    {
        if (!_parent.ContainsKey(x))
            _parent[x] = x;
        
        if (_parent[x] != x)
            _parent[x] = Find(_parent[x]);
        
        return _parent[x];
    }

    // 合并两个元素所在的集合
    public void Union(int x, int y)
    {
        int rootX = Find(x);
        int rootY = Find(y);
        
        if (rootX != rootY)
            _parent[rootY] = rootX;
    }
}

第二步：处理数对并生成最终结果 #

// 初始化你的数对列表
List<Tuple<int, int>> pairs = new List<Tuple<int, int>>
{
    Tuple.Create(1, 2),
    Tuple.Create(3, 4),
    Tuple.Create(3, 5),
    Tuple.Create(5, 6),
    Tuple.Create(10, 11),
    Tuple.Create(2, 3)
};

var uf = new UnionFind();

// 遍历所有数对，执行关联合并
foreach (var pair in pairs)
{
    uf.Union(pair.Item1, pair.Item2);
}

// 按根节点分组，整理成最终的集合列表
var groups = new Dictionary<int, List<int>>();
foreach (var num in uf._parent.Keys)
{
    int root = uf.Find(num);
    if (!groups.ContainsKey(root))
        groups[root] = new List<int>();
    groups[root].Add(num);
}

// 转换为你需要的List<List<int>>格式
var result = groups.Values.Select(g => g.OrderBy(n => n).ToList()).ToList();

// 验证输出
foreach (var group in result)
{
    Console.WriteLine($"{{{string.Join(", ", group)}}}");
}

逻辑说明 #

1. 路径压缩：Find方法会把元素直接指向根节点，后续查找操作的时间复杂度几乎是O(1)，处理大量数据时优势明显。
2. 合并逻辑：Union方法通过找到两个元素的根节点，将其中一个根节点挂载到另一个上，轻松完成集合合并，完全对应你描述的分步关联规则。
3. 结果整理：遍历所有元素，按根节点分组后排序，就能得到你想要的关联性集合。

这种方法比手动遍历判断合并要简洁得多，而且扩展性极强，就算后续添加更多数对也能高效处理。

内容的提问来源于stack exchange，提问作者José Luis