Description:

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to 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 graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

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 input.

Example 1:

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

Example 2:

Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]

We create an array parent to record each node's parent.

We use the union function to merge two nodes and the findParent function to find the root parent of each node.

If the root parents of two nodes are the same, it means the path will form a cycle, so we record it in ans.

At the end, return ans as answer.

If edges length is n, the time complexity is O(n*a(n))

/**
 * @param {number[][]} edges
 * @return {number[]}
 */
var findRedundantConnection = function (edges) {
    const parent = new Array(edges.length + 1).fill(0)

    for (let i = 0; i <= edges.length; i++) {
        parent[i] = i
    }

    const findParent = (x) => {
        if (parent[x] !== x) {
            parent[x] = findParent(parent[x])
        }
        return parent[x]
    }

    const union = (x, y) => {
        const rootX = findParent(x)
        const rootY = findParent(y)

        if (rootX === rootY) {
            return false
        }

        parent[rootX] = rootY
        return true
    }

    let ans = []
    for (const [u, v] of edges) {
        if (!union(u, v)) {
            ans = [u, v]
        }
    }

    return ans
};