Lstmxx的空间

685. 冗余连接 II

在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。

输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。

返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

链接

function findRedundantDirectedConnection(edges: number[][]): number[] {
  if (edges.length === 0) return []
  const len = edges.length
  const parent = Array(len + 1).fill(0)
  console.log(parent)
  // 旧边存放处
  const candidate1 = []
  // 新边存放处
  const candidate2 = []
  for (let i = 0; i < len; i++) {
    const [ u, v ] = edges[i]
    console.log(`${u}->${v}`)
    if (parent[v] === 0) {
      parent[v] = u
      console.log("yeah")
    } else {
      candidate1.push(parent[v])
      candidate1.push(v)
      candidate2.push(u)
      candidate2.push(v)
      edges[i][1] = 0
    }
  }
  console.log(parent)
  // 开始和上一道题一样查并集
  for(let i = 0; i < len; i++) {
    parent[i] = i
  }
  
  for(let i = 0; i < len; i++) {
    const [ u, v ] = edges[i]
    if (v === 0) continue
    const root = find(parent, u)
    // 如果通过u找到的根节点与v相同，则表明形成了环
    if (root === v) {
      // 没有入度为2的情况，即叶结点直接连在根节点上，所以直接删除就好了
      if (candidate1.length === 0) {
        return edges[i]
      }
      // 旧边有环，把旧边输出
      return candidate1
    }
    // 合并
    parent[v] = root
  }

  // 旧边形成的树没有形成环，那就是新的边有问题
  return candidate2
};

function find(parent: number[], index: number): number {
  if (parent[index] !== index) {
    parent[index] = find(parent, parent[index])
  }
  return parent[index]
}