Day56-图论，卡码网108，109

108. 冗余的边

• 题目描述：有一个图，它是一棵树，他是拥有 n 个节点（节点编号1到n）和 n - 1 条边的连通无环无向图，现在在这棵树上的基础上，添加一条边（依然是n个节点，但有n条边），使这个图变成了有环图，先请你找出冗余边，删除后，使该图可以重新变成一棵树。

• 输入描述：第一行包含一个整数 N，表示图的节点个数和边的个数。后续 N 行，每行包含两个整数 s 和 t，表示图中 s 和 t 之间有一条边。

• 输出描述：输出一条可以删除的边。如果有多个答案，请删除标准输入中最后出现的那条边。

• 输入示例
• 3
• 1 2
• 2 3
• 1 3
• 输出示例
• 1 3

---

• 思路

1. 初始化并查集
   • father[i] 表示节点 i 的父节点。
   • 初始化时，每个节点都是自己的父节点（即独立成集合）。
2. 查找根节点（路径压缩优化）
   • find(u)：查找 u 的根节点（代表该集合）。
   • 路径压缩优化：在查找过程中，直接将 u 的父节点指向根节点，减少后续查询时间。
3. 合并两个集合
   • join(u, v)：将 u 和 v 所在的集合合并。
   • 如果 u 和 v 已经在同一集合，直接返回（避免形成环）
4. 判断是否在同一集合
   • isSame(u, v)：判断 u 和 v 是否属于同一集合。
5. 主逻辑：读取输入并检测环
   • 流程：
     1. 读取节点数 N。
     2. 初始化并查集，每个节点独立成集合。
     3. 逐条读取边 (u, v)：
        • 如果 u 和 v 不在同一集合，合并它们。
        • 如果 u 和 v 已经在同一集合，说明这条边会形成环，输出 u v 并终止程序。

// 用于检测输入的无向图中是否存在 环。如果发现某条边的两个顶点已经在同一个集合中，说明这条边会形成环，程序会输出这条边并终止。

const r1 = require('readline').createInterface({ input: process.stdin });
// 创建readline接口
let iter = r1[Symbol.asyncIterator]();
// 创建异步迭代器
const readline = async () => (await iter.next()).value;

let N // 节点数和边数
let father = []  // 并查集

// 并查集初始化
const init = () => {
  for (let i = 1; i <= N; i++)  father[i] = i;
}

// 并查集里寻根的过程
const find = (u) => {
  return u == father[u] ? u : father[u] = find(father[u])
}

// 将v->u 这条边加入并查集
const join = (u, v) => {
  u = find(u)
  v = find(v)
  if (u == v) return // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
  father[v] = u
}

// 判断 u 和 v是否找到同一个根
const isSame = (u, v) => {
  u = find(u)
  v = find(v)
  return u == v
}

(async function () {
  // 读取第一行输入
  let line = await readline();
  N = Number(line);

  // 初始化并查集
  father = new Array(N)
  init()

  // 读取边信息, 加入并查集
  for (let i = 0; i < N; i++) {
    line = await readline()
    line = line.split(' ').map(Number)

    if (!isSame(line[0], line[1])) {
      join(line[0], line[1])
    }else{
      console.log(line[0], line[1]);
      break
    }
  }
})()

---

---

109. 冗余的边II

• 题目描述：有一种有向树,该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。有向树拥有 n 个节点和 n - 1 条边。现在有一个有向图，有向图是在有向树中的两个没有直接链接的节点中间添加一条有向边。输入一个有向图，该图由一个有着 n 个节点(节点编号 从 1 到 n)，n 条边，请返回一条可以删除的边，使得删除该条边之后该有向图可以被当作一颗有向树。

• 输入描述：第一行输入一个整数 N，表示有向图中节点和边的个数。 后续 N 行，每行输入两个整数 s 和 t，代表这是 s 节点连接并指向 t 节点的单向边

• 输出描述：输出一条可以删除的边，若有多条边可以删除，请输出标准输入中最后出现的一条边。

• 输入示例
• 3
• 1 2
• 1 3
• 2 3
• 输出示例
• 2 3

---

• 思路

• 有向树的性质，如果是有向树的话，只有根节点入度为0，其他节点入度都为1（因为该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点）。

• 三种情况

  • 1. 情况一，找到入度为2的点，那么删一条指向该节点的边，如果是删哪个都可以，优先删顺序靠后的边（从后向前遍历，因为如果两条边删哪一条都可以成为树，就删最后那一条。）。如 1=》2，1=》3，2=》3，3入度为2，删2，3
  • 2. 入度为2 还有一种情况，情况二，只能删特定的一条边。如 1=》3，4=》3，3=》2，2=》1，只能删1，3
  • 3. 情况三，如果没有入度为2的点，说明 图中有环了（有向环），删掉构成环的边。如 1=》3，3=》2，2=》1，删最后出现的一条边

/**
 * 算法流程
1. 统计入度：找到所有节点的入度。
2. 检查是否有节点入度为 2：
    如果有，尝试删除其中一条边，检查是否成树。
3. 如果没有入度为 2 的节点：
    直接找第一条形成环的边删除。
 */
const r1 = require('readline').createInterface({ input: process.stdin });
// 创建readline接口
let iter = r1[Symbol.asyncIterator]();
// 创建异步迭代器
const readline = async () => (await iter.next()).value;

let N // 节点数和边数
let father = []  // 并查集
let edges = [] // 边集
let inDegree = [] // 入度

// 并查集初始化
const init = () => {
  for (let i = 1; i <= N; i++)  father[i] = i;
}

// 并查集里寻根的过程
const find = (u) => {
  return u == father[u] ? u : father[u] = find(father[u])
}

// 将v->u 这条边加入并查集
const join = (u, v) => {
  u = find(u)
  v = find(v)
  if (u == v) return // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
  father[v] = u
}

// 判断 u 和 v是否找到同一个根
const isSame = (u, v) => {
  u = find(u)
  v = find(v)
  return u == v
}

// 判断删除一条边后是不是树
const isTreeAfterRemoveEdge = (edges, edge) => {
  // 初始化并查集
  init()

  for (let i = 0; i < N; i++) {
    if (i == edge) continue
    if (isSame(edges[i][0], edges[i][1])) { // 构成有向环了，一定不是树
      return false
    }
    join(edges[i][0], edges[i][1])
  }
  return true
}

// 在有向图里找到删除的那条边, 使其成为树
const getRemoveEdge = (edges) => {
  // 初始化并查集
  init()

  for (let i = 0; i < N; i++) {
    if (isSame(edges[i][0], edges[i][1])) { // 构成有向环了，就是要删除的边
      console.log(edges[i][0], edges[i][1]);
      return
    } else {
      join(edges[i][0], edges[i][1])
    }
  }
}

(async function () {
  // 读取第一行输入
  let line = await readline();
  N = Number(line);

  // 读取边信息, 统计入度
  for (let i = 0; i < N; i++) {
    line = await readline()
    line = line.split(' ').map(Number)

    edges.push(line)

    inDegree[line[1]] = (inDegree[line[1]] || 0) + 1
  }

  // 找到入度为2的节点
  let vec = []  // 记录入度为2的边（如果有的话就两条边）
  // 找入度为2的节点所对应的边，注意要倒序，因为优先删除最后出现的一条边
  for (let i = N - 1; i >= 0; i--) {
    if (inDegree[edges[i][1]] == 2) {
      vec.push(i)
    }
  }

  // 情况一、情况二
  if (vec.length > 0) {
     // 放在vec里的边已经按照倒叙放的，所以这里就优先删vec[0]这条边
    if (isTreeAfterRemoveEdge(edges, vec[0])) {
      console.log(edges[vec[0]][0], edges[vec[0]][1]);
    } else {
      console.log(edges[vec[1]][0], edges[vec[1]][1]);
    }
    return 0
  }

  // 情况三
  // 明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了
  getRemoveEdge(edges)
})()

---

---

---

参考&感谢各路大神

• 代码随想录
• B站：代码随想录