This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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:**

**Update (2017-09-26):**

We have overhauled the problem description + test cases and specified clearly the graph is an ** undirected** graph. For the

b'

\n\n#### Approach #1: DFS [Accepted]

\n

\n#### Approach #2: Union-Find [Accepted]

\n

\n

'
**Intuition and Algorithm**

For each edge `(u, v)`

, traverse the graph with a depth-first search to see if we can connect `u`

to `v`

. If we can, then it must be the duplicate edge.

**Complexity Analysis**

- \n
- \n
Time Complexity: where is the number of vertices (and also the number of edges) in the graph. In the worst case, for every edge we include, we have to search every previously-occurring edge of the graph.

\n \n - \n
Space Complexity: . The current construction of the graph has at most nodes.

\n \n

\n

**Intuition and Algorithm**

If we are familiar with a Disjoint Set Union (DSU) data structure, we can use this in a straightforward manner to solve the problem: we simply find the first edge occurring in the graph that is already connected. The rest of this explanation will focus on the details of implementing DSU.

\nA DSU data structure can be used to maintain knowledge of the connected components of a graph, and query for them quickly. In particular, we would like to support two operations:

\n- \n
- \n

\n`dsu.find(node x)`

, which outputs a unique id so that two nodes have the same id if and only if they are in the same connected component, and: \n - \n

\n`dsu.union(node x, node y)`

, which draws an edge`(x, y)`

in the graph, connecting the components with id`find(x)`

and`find(y)`

together. \n

To achieve this, we keep track of `parent`

, which remembers the `id`

of a smaller node in the same connected component. If the node is it\'s own parent, we call this the *leader* of that connected component.

A naive implementation of a DSU structure would look something like this:

\n*Psuedocode*

We use two techniques to improve the run-time complexity: *path compression*, and *union-by-rank*.

- \n
- \n
Path compression involves changing the

\n`x = parent[x]`

in the`find`

function to`parent[x] = find(parent[x])`

. Basically, as we compute the correct leader for x, we should remember our calculation. \n - \n
Union-by-rank involves distributing the workload of

\n`find`

across leaders evenly. Whenever we`dsu.union(x, y)`

, we have two leaders`xr, yr`

and we have to choose whether we want`parent[x] = yr`

or`parent[y] = xr`

. We choose the leader that has a higher following to pick up a new follower.

\nSpecifically, the meaning of`rank`

is that there are less than`2 ^ rank[x]`

followers of`x`

. This strategy can be shown to give us better bounds for how long the recursive loop in`dsu.find`

could run for. \n

*Alternate Implementation of DSU without Union-By-Rank*\n

**Complexity Analysis**

- \n
- \n
Time Complexity: , where is the number of vertices (and also the number of edges) in the graph, and is the

\n*Inverse-Ackermann*function. We make up to queries of`dsu.union`

, which takes (amortized) time. Outside the scope of this article, it can be shown why`dsu.union`

has complexity, what the Inverse-Ackermann function is, and why is approximately . \n - \n
Space Complexity: . The current construction of the graph (embedded in our

\n`dsu`

structure) has at most nodes. \n

\n

Analysis written by: @awice

\n