业务场景

隧道里有多条平行的测线，相邻两条（编号差 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)，几千个病害也就是眨眼的事。

后面再碰到类似的活——社交网络分簇、等价类合并、连通分量——都可以照这个套路上并查集，比写图遍历或者两两聚类都省事。