业务场景

隧道里有多条平行测线，相邻两条测线（编号相差 1）上如果各有一个病害，且里程范围有重叠，很可能是同一个病害在两条测线上的不同反映——这种要标成“共有病害”。

难点：传递性

判断不能只做两两配对。因为重叠有传递性：A 和 B 重叠、B 和 C 重叠，那 A/B/C 实际上是同一组，应该归到一起。如果只两两标记，A-B 一组、B-C 一组，C 和 A 的关系就丢了，分组是碎的。

并查集（Union-Find）

这种“传递性分组”正是并查集的拿手好戏：

class UnionFind(n: Int) {
    val parent = IntArray(n) { it }
    val rank = IntArray(n)

    fun find(x: Int): Int {
        if (parent[x] != x) parent[x] = find(parent[x])   // 路径压缩
        return parent[x]
    }

    fun union(a: Int, b: Int) {
        val ra = find(a); val rb = find(b)
        if (ra == rb) return
        if (rank[ra] < rank[rb]) parent[ra] = rb          // 按秩合并
        else if (rank[ra] > rank[rb]) parent[rb] = ra
        else { parent[rb] = ra; rank[ra]++ }
    }
}

流程：

  1. 检测所有相邻测线、里程重叠的病害对。
  2. 对每一对调 union(a, b)。
  3. 最后 find(x) 相同的病害就是同一组。

加了路径压缩 + 按秩合并后，每次 find/union 接近 O(1)，几千个病害也是瞬间完成。

小结

凡是“有关系就连通、要整体分组”的场景——共有病害、社交网络分簇、等价类合并——并查集都是首选，比图遍历或两两聚类都简洁高效。