并查集典型题：冗余连接与岛屿合并

并查集典型题：冗余连接与岛屿合并

一、面试常考点

1. 冗余连接

当 union(u, v) 返回 false，说明这条边造成环。（深入阅读：1. 环检测）

2. 动态岛屿

每次把水域变陆地并与周围陆地合并，维护岛屿数量。（深入阅读：2. 岛屿合并）

二、细节介绍

1. 环检测

适合无向图加边判环。

2. 岛屿合并

二维坐标可映射成一维 id。

三、示例代码（冗余连接）

function findRedundantConnection(edges) {
  const n = edges.length
  const dsu = new DSU(n + 1)

  for (const [u, v] of edges) {
    if (!dsu.union(u, v)) return [u, v]
  }

  return []
}

四、常用应用场景

1. 网络拓扑检测

发现多余链路或异常闭环。

2. 地图连通域维护

实时合并区域。