本文共 4113 字，大约阅读时间需要 13 分钟。
In this problem, a tree is an undirected graph that is connected and has no cycles.
The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.
The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.
Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v.
Example 1:
Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: The given undirected graph will be like this: 1 / \ 2 - 3 Example 2: Input: [[1,2], [2,3], [3,4], [1,4], [1,5]] Output: [1,4] Explanation: The given undirected graph will be like this: 5 - 1 - 2 | | 4 - 3 Note: The size of the input 2D-array will be between 3 and 1000. Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.Update (2017-09-26):
We have overhauled the problem description + test cases and specified clearly the graph is an undirected graph. For the directed graph follow up please see Redundant Connection II). We apologize for any inconvenience caused.来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/redundant-connection 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
去掉无向图的一条边，让它变成一棵树。如果有多条边可以去，那么就返回数组中最后出现的边。
先找出环中的所有节点：相当于拓扑排序，每次都清除掉入度是1的节点，看最后剩下的节点，从数组中找到最后出现的。
class Solution { boolean [][]graph; int lenght = 0; Stack >stack = new Stack<>(); public int[] findRedundantConnection(int[][] edges) { lenght = edges.length; int[]record = new int[edges.length + 1]; for (int i = 0; i < edges.length; i++) { record[edges[i][0]]++; record[edges[i][1]]++; } graph = new boolean[edges.length + 1][edges.length + 1]; for (int i = 0; i < edges.length; i++) { graph[edges[i][0]][edges[i][1]] = true; graph[edges[i][1]][edges[i][0]] = true; } Queue queue = new ArrayDeque<>(); for (int i = 1; i <= lenght; i++) { if (record[i] == 1) { queue.add(i); record[i]--; } } while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { int t = queue.poll(); for (int j = 1; j <= lenght; j++) { if (graph[t][j]) { record[j]--; } if (record[j] == 1) { record[j]--; queue.add(j); } } } } int []ans = new int[2]; for (int i = edges.length - 1; i >= 0; i--) { for (int j = 1; j <= lenght; j++) { if (record[j] > 1) { if (edges[i][0] == j || edges[i][1] == j) { if (record[edges[i][0]] > 1 && record[edges[i][1]] > 1 ) { ans[0] = edges[i][0]; ans[1] = edges[i][1]; return ans; } } } } } return null; }} 这题的另外一个方法，用一个数组root储存节点的关联，比如若 root[1] = 2，就表示1和2是相连的，root[2] = 3 表示2和3是相连的，如果新加 [1, 3] 的话，通过 root[1] = 2，再通过 root[2] = 3，说明1能到结点3，环是存在的；如果没有，那么要将1和3关联起来，让 root[1] = 3
class Solution { public int[] findRedundantConnection(int[][] edges) { int [] root = new int[edges.length + 1]; Arrays.fill(root, -1); for (int[] edge : edges) { int x = find(root, edge[0]); int y = find(root, edge[1]); if (x == y) return edge; root[x] = y; } return null; } public int find(int []root, int i) { while (root[i] != -1) { i = root[i]; } return i; }}