Graph Breadth First Search Depth First Search Shortest Path Minimum Spanning Tree
Proficient Level

Implement the findRedundantConnection method that returns the edge that creates a cycle in an undirected graph.

You are given an undirected graph that started as a tree and then had one extra edge added. The edges are provided as pairs [u, v].

Return the edge that can be removed so the graph becomes a tree again. If multiple answers appear possible while scanning, return the first edge that creates a cycle in the given order.

Example 1
Input:
edges (int[][]) = [[1,2],[1,3],[2,3]]
size (int) = 3
Return:
(int[]) [2,3]
Example 2
Input:
edges (int[][]) = [[1,2],[2,3],[3,4],[1,4],[1,5]]
size (int) = 5
Return:
(int[]) [1,4]
Example 3
Input:
edges (int[][]) = [[1,2],[2,3],[1,3]]
size (int) = 3
Return:
(int[]) [1,3]

Use the Union-Find data structure.

For every edge, check whether both nodes already belong to the same connected component. If they do, adding that edge creates a cycle, so that edge is the answer. Otherwise, union the two components and continue.

Path compression and union by rank keep the operations efficient.

Pseudocode:

function findRedundantConnection(edges, size):
    initialize parent for each node
    for each edge [u, v] in edges:
        rootU = find(u)
        rootV = find(v)
        if rootU == rootV:
            return [u, v]
        union(rootU, rootV)
    return []
Run your code to see the result.