684. 冗余连接

题目

输入一个图，该图由一个有着 N 个节点 (节点值不重复 1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在 1 到 N 中间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足  u < v，表示连接顶点 u 和 v 的无向图的边。

返回一条可以删去的边，使得结果图是一个有着 N 个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式  u < v。

题解

深度优先遍历

/**
 * @param {number[][]} edges
 * @return {number[]}
 */
var findRedundantConnection = function(edges) {
  let adj = [];

  for (let e of edges) {
    let u = e[0],
      v = e[1];
    if (adj[u] && adj[v]) {
      let visited = [];
      // 深度优先遍历 如果已经存在一条路径就返回
      if (dfs(u, v, visited, adj)) return e;
    }
    // 没有回路就向邻接表中添加
    addAdj(u, v, adj);
    addAdj(v, u, adj);
  }
  return null;
};

function addAdj(u, v, adj) {
  if (!adj[u]) adj[u] = [];
  adj[u].push(v);
}

// 深度优先搜索 如果能找到从 start 到 end 的路径就返回 true 反之 false
function dfs(start, end, visited, adj) {
  if (start == end) return true;
  visited[start] = true;
  for (let n of adj[start]) {
    if (!visited[n]) {
      if (dfs(n, end, visited, adj)) return true;
    }
  }
  return false;
}