LeetCode684. Redundant Connectio

1、题目链接

https://leetcode.com/problems/redundant-connection/

2、解题思路

这道题的意思是说，给你一个二维数组，这个二维数组代表一个图，这个图由一颗有着N个节点的树再加一条附加边构成，[[a1, b1], [a2, b2], [a3, b3]]，也就是说二维数组里面的每一项都是图的一条边，让你返回某一条边，当这条边删除之后使得剩下的节点是一棵树，如果有多个答案的话，就返回最后一个；换句话说，这个图中有一个闭环，然后让你找出一条可以删除的边，使其成为一棵树，这样的话我们就可以来分析一下，怎么知道他是一个闭环呢？

如上图所示，我们只需要找到其中一条边两个节点的顶点（即根结点）相同即可，那么我们怎么保证它是最后一条呢？因为题目说了只有一条附加边；所以我们先遍历整个二维数组，也就是图的边，然后每次都把边的两个顶点找出来，通过一个数组来记录，假设 nums[a] = b，那么就有a的顶点是b，通过这种数据存储的方式我们最终可以递归算出某条边两个节点的顶点，如果这两个节点的顶点相同，那么我们就返回这条边，这条边就是附加边，如果顶点不相同，那么我们将较小节点的根结点置为较大的那个节点。

3、代码

• Java

public int[] findRedundantConnection(int[][] edges) {
    int[] nums = new int[1001];
    for (int i = 0; i < edges.length; i++) {
        int root1 = findRoot(edges[i][0], nums);  //通过递归找第一个节点的根结点
        int root2 = findRoot(edges[i][1], nums);  //通过递归找第二个节点的根结点
        if (root1 == root2) {  //如果两个节点的根结点相同，那么说明有环
            return edges[i];
        } else {
            nums[root1] = root2;  //如果两个根结点不相同，那么将第一个节点的根结点置为第二个节点
        }
    }
    return new int[]{0, 1};
}
public int findRoot(int x, int[] nums) {
    if (nums[x] == 0) return x;
    x = nums[x];
    return findRoot(x,nums);
}

4、提交结果