Press "Enter" to skip to content

花花酱 LeetCode 684. Redundant Connection


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:

Example 2:



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

DFS / Union-Find



C++ / DFS


C++ / Union Find

Java / Union Find


Python: Union Find

Python / Union Find V2



If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website


One Comment

  1. haoxianghua haoxianghua June 19, 2018

    in the union function, the rank isn’t updated

Leave a Reply