Solution: Redundant Connection

Statement

We’re given an undirected graph consisting of nn nodes. The graph is represented as an array called edges, of length nn, where edges[i] = [a, b] indicates that there is an edge between nodes a and b in the graph.

Return an edge that can be removed to make the graph a treeA tree is an undirected graph that is connected and has no cycles. of nn nodes. If there are multiple candidates for removal, return the edge that occurs last in edges.

Constraints:

  • 3≤3 \leq nn ≤1000\leq 1000
  • edges.length== nn
  • edges[i].length == 2
  • 1≤1 \leq a << b ≤n\leq n
  • a≠ba \neq b
  • There are no repeated edges.
  • The given graph is connected.
  • The graph contains only one cycle.

Solution

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

We can solve this problem using techniques like DFS or BFS, however, the naive approach using DFS or BFS has a time complexity of O(n2)O(n^2) in the worst-case scenario. This is because the DFS or BFS algorithm will explore the graph by visiting each node and its edges, which may result in visiting many nodes multiple times, and not necessarily finding the redundant connection in an efficient manner.

Optimized approach using union find

We are going to solve this problem with the help of the union find pattern and will be using union by rank and path compression.

  • Union by rank: We connect the nodes that come afterward to the nodes that came before them. This allows us to add new nodes to the subset of the representative node of the larger connected component. Using ranks to connect nodes in this manner helps reduce the depth of the recursion call stack of the find function, since the trees within each disjoint set remain relatively shallow.

  • Path compression: On each find operation on a node of a tree, we update the parent of that node to point directly to the root. This reduces the length of the path of that node to the root, ensuring we don’t have to travel all the intermediate nodes on future find operations.

The slides below illustrate how the algorithm runs:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.