Redundant Connection II
The problem describes a rooted tree that has one additional edge, which makes it no longer a valid tree. We are asked to find and return the extra edge.
Here’s a Python function:


This function first identifies any nodes with two parents. It then uses a UnionFind algorithm to detect cycles in the graph. Depending on whether a node with two parents is found, it returns the redundant edge accordingly.
Identifying Problem Isomorphism
“Redundant Connection II” can be related to a group of problems that deal with detecting cycles and understanding directed graph structures.
A simpler problem in this category is “Course Schedule”. In this problem, you are asked if it’s possible to finish all courses given a list of prerequisite pairs. This problem is simpler because it requires detection of a cycle in a directed graph, which is part of “Redundant Connection II”, but does not require the identification of a specific edge causing the cycle.
A more complex problem is “Find Eventual Safe States”. This problem asks you to find all the nodes in a graph from which we can reach a terminal node (a node that leads to no other node). It’s more complex because it involves not just cycle detection, but also safe node identification in a directed graph.
The reasoning behind these selections:
“Course Schedule” involves cycle detection in a directed graph, which is a primary component of “Redundant Connection II”. However, it is simpler because it doesn’t need to identify the redundant edge causing the cycle.
“Find Eventual Safe States” includes the component of cycle detection, but adds an extra layer of complexity with the task of identifying safe states. This requires a more nuanced understanding of graph traversal and the implications of cycles on the graph’s structure.
So, the order of problems from simpler to more complex, based on understanding of cycles and directed graph structures, would be:
 “Course Schedule”
 “Redundant Connection II”
 “Find Eventual Safe States”
This mapping is an approximation. While these problems share a theme of cycles and directed graph structures, the specific problem constraints and details can influence the complexity and solution approach.
10 Prerequisite LeetCode Problems
Here are 10 problems that you can solve to prepare for tackling problem 685, “Redundant Connection II”:
LeetCode 684. Redundant Connection: In this problem, the edges are undirected. It is a simplified version of the problem you’re trying to solve.
LeetCode 547. Number of Provinces: This problem requires understanding of the Disjoint Set/UnionFind concept.
LeetCode 200. Number of Islands: Classic problem to understand depthfirst search (DFS) and breadthfirst search (BFS) on a 2D grid.
LeetCode 261. Graph Valid Tree: This problem helps to understand the concept of detecting cycles in an undirected graph.
LeetCode 323. Number of Connected Components in an Undirected Graph: This problem involves finding connected components, which can be solved with DFS, BFS, or UnionFind.
LeetCode 959. Regions Cut By Slashes: In this problem, you would learn to convert a 2D grid to a graph and apply UnionFind.
LeetCode 721. Accounts Merge: This problem can be solved using UnionFind and it requires an understanding of how to handle strings and lists in the UnionFind data structure.
LeetCode 305. Number of Islands II: This problem is an extension of “Number of Islands” with the ability to add land incrementally and count islands after each addition.
LeetCode 1559. Detect Cycles in 2D Grid: This problem is about detecting cycles in a 2D grid, which is somewhat similar to what you have to do in problem 685.
LeetCode 765. Couples Holding Hands: This problem requires understanding of graph theory and UnionFind to solve a realworld problem. The problem is a harder one, but it’s a good way to test your skills after going through simpler ones.
Understand the UnionFind or Disjoint Set Union (DSU) concept, which will be crucial to solve problem 685.


Problem Classification
The problem can be classified into the domain of graph theory, specifically dealing with trees and directed edges. This problem can be viewed as an exercise in graph manipulation, validation and cycle detection.
Here are the ‘What’ components:
 We are given a directed graph, represented as a 2D array of edges. The graph originally started as a rooted tree with n nodes (with distinct values from 1 to n).
 An additional edge is added between two distinct vertices, which was not an edge that already existed. This creates a scenario where the graph no longer forms a rooted tree.
 We need to find and return an edge that, when removed, will transform the graph back into a rooted tree of n nodes. If there are multiple possibilities, we should return the one that occurs last in the given 2D array of edges.
This can be further categorized as a graph traversal problem with aspects of cycle detection and edge removal. A potential algorithm to solve this problem would have to traverse the graph, detect the cycle caused by the additional edge, and then determine the correct edge to remove.
This problem falls under the category of “Graph Theory”. More specifically, it deals with finding a redundant directed edge in a graph.
Graphs  The problem involves a graph where vertices and edges are defined.
Directed Graph  The graph in the problem is a directed one, meaning the edges have a specific direction, from one node to another, and are not bidirectional.
Cycles in Graph  A cycle in a graph is a nonempty trail in which the only repeated vertices are the first and last vertices. This problem involves detecting a cycle in the graph.
Redundant Edge  An edge in a graph is said to be redundant if removing it does not affect the connectivity of the graph. The goal of the problem is to find such a redundant edge in the directed graph.
UnionFind Algorithm  The problem description does not explicitly state it, but it suggests using a UnionFind data structure or algorithm to efficiently manage and query connected components of the graph.
Remember, these are domain classifications and concepts that the problem touches upon. They may or may not directly hint at the solution strategy or the data structures and algorithms used in the solution. The actual solution approach might require combining these concepts with appropriate algorithmic strategies and data structures.
Language Agnostic Coding Drills
Understanding the problem domain: This problem is about graph theory and specifically about detecting cycles and duplicate edges in a directed graph.
Understanding UnionFind Data Structure: This data structure is essential for solving this problem. It allows to efficiently check if two nodes are in the same set (connected) and to unite two sets.
Initializing the UnionFind Data Structure: Here, we initialize a list to represent the parent node of each node in the graph.
Understanding how the “find” operation works: This function returns the root of the tree that a given node belongs to. It does so by following parent pointers until it reaches the root.
Understanding how the “union” operation works: This function unites the sets that two nodes belong to. It does this by making the root of one set point to the root of the other set.
Detecting a loop in the graph: We iterate over the edges, and for each edge, we check if its nodes are already in the same set. If they are, it means that we’ve found a loop.
Tracking parents of each node: This step is for detecting nodes with two parents. If a node has two parents, we record them.
Detecting nodes with two parents: We find nodes with two parents by looking for nodes that have two entries in the parent dictionary.
Deciding which edge to remove: If a node has two parents but there is no loop, we remove the edge that was discovered later. If there is a loop and no node has two parents, we remove the edge that creates the loop. If there is a loop and a node has two parents, we need to decide between two candidate edges to remove: we try removing the second one first, and if this doesn’t break the loop, we remove the first one.
In the actual solution, these steps would be performed in an intertwined manner, but for learning purposes, you could practice each of these concepts separately.
Targeted Drills in Python
Understanding the problem domain: This step doesn’t have a specific code, but you should understand what is directed graph, what is a cycle, and what is a duplicate edge in the context of a directed graph.
Understanding UnionFind Data Structure: Here’s a simple implementation of a UnionFind data structure:
1 2 3 4 5 6 7 8 9 10 11
class UnionFind: def __init__(self, size): self.parent = list(range(size)) def find(self, x): if x != self.parent[x]: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): self.parent[self.find(x)] = self.find(y)
Initializing the UnionFind Data Structure:
1
uf = UnionFind(5) # Initialize for 5 nodes
Understanding how the “find” operation works:
1
print(uf.find(1)) # Print the set to which node 1 belongs
Understanding how the “union” operation works:
1
uf.union(1, 2) # Unite the sets that nodes 1 and 2 belong to
Detecting a loop in the graph:
1 2 3 4 5
edges = [(0, 1), (1, 2), (2, 0)] # Example graph with a loop for x, y in edges: if uf.find(x) == uf.find(y): print("Loop detected") uf.union(x, y)
Tracking parents of each node:
1 2 3
parents = {} for x, y in edges: parents.setdefault(y, []).append(x)
Detecting nodes with two parents:
1 2
two_parents = [node for node, parent in parents.items() if len(parent) > 1] print(two_parents)
Deciding which edge to remove: This is a complex drill and is closely tied to the specific problem at hand. Here’s an simplified example:
1 2 3 4 5 6 7 8 9 10 11
def remove_edge(edges, edge_to_remove): return [edge for edge in edges if edge != edge_to_remove] if two_parents: edge_to_remove = (parents[two_parents[0]][1], two_parents[0]) edges = remove_edge(edges, edge_to_remove) else: for edge in edges[::1]: if uf.find(edge[0]) == uf.find(edge[1]): edges = remove_edge(edges, edge) break
These are the basic coding drills for each unit of learning. The actual problem solution involves combining these units in a complex manner, with additional logic to handle the specific requirements of the problem.