C#实现List对象按双属性关联关系连通分组的方法

这个需求本质是无向图连通分量识别问题：每个提交字符串是图的节点，每条配对记录是连接两个节点的无向边，最终要把同属一个连通分量的所有边（配对记录）归为同一组。
最适合这个场景的实现是用并查集（Disjoint Set Union, DSU）结构，合并和查找连通关系的效率极高，代码逻辑也简单，不会出现多层遍历漏判关联关系的问题。

1. 基础类定义 #

注意你给出的示例JSON属性名带尾随空格，反序列化时记得加特性映射，否则会拿不到属性值：

// 用System.Text.Json反序列化的话加下面的特性，用Newtonsoft.Json换[JsonProperty]即可
public class TopComparison
{
    [JsonPropertyName("first_submission ")]
    public string first_submission { get; set; }
    [JsonPropertyName("second_submission ")]
    public string second_submission { get; set; }
}

2. 并查集辅助类 #

public class UnionFind
{
    // 存储节点的父节点映射
    private readonly Dictionary<string, string> _parent = new();
    // 查找节点根节点，带路径压缩优化
    private string Find(string node)
    {
        if (!_parent.ContainsKey(node))
            _parent[node] = node;
        if (_parent[node] != node)
            _parent[node] = Find(_parent[node]);
        return _parent[node];
    }
    // 合并两个节点所在的连通集合
    public void Union(string nodeA, string nodeB)
    {
        string rootA = Find(nodeA);
        string rootB = Find(nodeB);
        if (rootA != rootB)
            _parent[rootB] = rootA;
    }
    // 获取节点所属连通分量的唯一标识（根节点）
    public string GetGroupKey(string node) => Find(node);
}

3. 分组逻辑实现 #

public List<List<TopComparison>> GroupTopComparisons(List<TopComparison> source)
{
    var uf = new UnionFind();
    // 第一遍遍历：合并所有关联节点
    foreach (var item in source)
    {
        // 跳过空值记录，避免抛异常
        if (string.IsNullOrWhiteSpace(item.first_submission) || string.IsNullOrWhiteSpace(item.second_submission))
            continue;
        uf.Union(item.first_submission, item.second_submission);
    }
    // 第二遍遍历：按连通分量分组
    var groupDict = new Dictionary<string, List<TopComparison>>();
    foreach (var item in source)
    {
        if (string.IsNullOrWhiteSpace(item.first_submission) || string.IsNullOrWhiteSpace(item.second_submission))
            continue;
        // 同一条记录的两个节点属于同一连通分量，取任意一个的分组key即可
        string groupKey = uf.GetGroupKey(item.first_submission);
        if (!groupDict.ContainsKey(groupKey))
            groupDict[groupKey] = new List<TopComparison>();
        groupDict[groupKey].Add(item);
    }
    // 转成需要的嵌套列表格式返回
    return groupDict.Values.ToList();
}

• 如果需要忽略大小写做关联匹配（比如示例里的harry和Harry判定为同一个键），只要把并查集中的字典初始化改成传入大小写不敏感的比较器即可：

  private readonly Dictionary<string, string> _parent = new(StringComparer.OrdinalIgnoreCase);
  

• 该实现自动支持多层关联传递，比如A-B、B-C、C-D、D-E这类链式关联的记录，会全部被归到同一组，没有关联层数限制。
• 传入测试数据集运行后，会得到和期望完全一致的3个分组结果。

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