LeetCode 685: Redundant Connection II Solution in Python – A Step-by-Step Guide

What Is LeetCode 685: Redundant Connection II?

In LeetCode 685: Redundant Connection II, you’re given a list edges of integer pairs [u, v], representing directed edges from node u to node v in a graph with n nodes. The graph has n edges, forming a rooted tree (n-1 edges, one root with in-degree 0, others with in-degree 1) plus one extra edge that creates either a cycle or a node with two parents. Your task is to find the redundant edge that, when removed, makes the graph a valid rooted tree. Return this edge as an array [u, v] (the one appearing last in the input if multiple exist). For example, with edges = [[1, 2], [2, 3], [3, 1], [4, 1]], removing [4, 1] eliminates a second parent at node 1, leaving a tree rooted at 4, so return [4, 1]. This problem tests your ability to handle cycles and in-degree issues in a directed graph efficiently.

Problem Statement

• Input:
• edges: List of lists, where each inner list [u, v] is a directed edge.
• Output: A list [u, v]—the redundant edge to remove.
• Rules:
• Graph has n nodes and n edges (tree + 1 edge).
• Nodes numbered 1 to n.
• Return edge causing cycle or second parent, last in input if multiple.
• Resulting graph must be a rooted tree (one root with in-degree 0, others 1).

Constraints

• n == edges.length.
• 4 ≤ n ≤ 10⁴.
• edges[i].length == 2.
• 1 ≤ edges[i][0], edges[i][1] ≤ n.
• No duplicate edges.

Examples

• Input: edges = [[1, 2], [1, 3], [2, 3]]
• Output: [2, 3] (Removes cycle 1-2-3)
• Input: edges = [[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]]
• Output: [4, 1] (Removes cycle 1-2-3-4)
• Input: edges = [[1, 2], [2, 3], [3, 1], [4, 1]]
• Output: [4, 1] (Removes second parent at 1)

These examples set the graph—let’s solve it!

Understanding the Problem: Untangling the Graph

To solve LeetCode 685: Redundant Connection II in Python, we need to identify the redundant edge in a directed graph with n nodes and n edges that prevents it from being a rooted tree, either by forming a cycle or giving a node two parents. A brute-force approach—testing each edge removal—would be O(n²), inefficient for n ≤ 10⁴. Since we’re dealing with directed edges and need to ensure a tree structure, Union-Find with in-degree tracking or DFS can optimize this. We’ll use:

• Best Solution (Union-Find with In-Degree Tracking): O(n * α(n)) time, O(n) space—near-linear and optimal.
• Alternative Solution (DFS with Cycle and In-Degree Check): O(n²) time, O(n) space—intuitive but slower.

Let’s start with the Union-Find solution, breaking it down for beginners.

Best Solution: Union-Find with In-Degree Tracking

Why This Is the Best Solution

The Union-Find with in-degree tracking approach is the top choice for LeetCode 685 because it’s highly efficient—O(n * α(n)) time with O(n) space, where α(n) is the inverse Ackermann function, nearly constant—and elegantly handles both cycle and two-parent cases by combining Union-Find for cycle detection with in-degree checks to identify nodes with multiple incoming edges. It fits constraints (n ≤ 10⁴) perfectly and is intuitive once you see the logic. It’s like connecting nodes while watching for loops and double bookings!

How It Works

Think of this as a graph pruner:

• Step 1: Check In-Degrees:
• Build indegree array, track node with in-degree 2 (conflict).
• Record edges causing conflict (candidate1, candidate2).
• Step 2: Initialize Union-Find:
• parent[i] = i, rank[i] = 0.
• Step 3: Find and Union:
• find(x): Root with path compression.
• union(u, v): Merge sets, return False if cycle.
• Step 4: Process Edges:
• If in-degree 2 exists:
• Try union skipping candidate1, check cycle with candidate2.
• If cycle, return candidate1; else, return candidate2.
• If no in-degree 2, return edge causing cycle.
• Step 5: Return Result:
• Return redundant edge.

It’s like a parent checker—track and prune!

Step-by-Step Example

Example: edges = [[1, 2], [2, 3], [3, 1], [4, 1]]

• Step 1: In-degree:
• indegree = [0, 2, 1, 1, 0] (node 1 has 2 parents).
• candidate1 = [3, 1], candidate2 = [4, 1] (later edge).
• Step 2: Init:
• parent = [0, 1, 2, 3, 4], rank = [0, 0, 0, 0, 0].
• Step 3: Process skipping candidate1 ([3, 1]):
• [1, 2]: union(0, 1), parent[1] = 0.
• [2, 3]: union(1, 2), parent[2] = 0 (via 1).
• [4, 1]: union(3, 0), parent[0] = 3, parent = [3, 0, 0, 3, 4].
• Step 4: Check cycle with candidate2 ([4, 1]):
• Already processed, check candidate1:
• Reset, process all: [1, 2], [2, 3], [3, 1] (cycle), [4, 1] (two parents).
• [4, 1] is last conflict, return it.
• Step 5: Return [4, 1].
• Output: [4, 1].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        # Step 1: Track in-degrees and candidates
        n = len(edges)
        indegree = [0] * (n + 1)  # 1-based nodes
        candidate1, candidate2 = None, None

        for u, v in edges:
            indegree[v] += 1
            if indegree[v] == 2:
                if not candidate1:
                    candidate1 = [u, v]
                else:
                    candidate2 = [u, v]

        # Step 2: Initialize Union-Find
        parent = list(range(n + 1))
        rank = [0] * (n + 1)

        # Step 3: Find and Union functions
        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(u: int, v: int) -> bool:
            root_u = find(u)
            root_v = find(v)
            if root_u == root_v:
                return False
            if rank[root_u] < rank[root_v]:
                parent[root_u] = root_v
            elif rank[root_u] > rank[root_v]:
                parent[root_v] = root_u
            else:
                parent[root_v] = root_u
                rank[root_u] += 1
            return True

        # Step 4: Process edges
        if candidate2:  # Two parents case
            # Try skipping candidate1, check cycle with candidate2
            for u, v in edges:
                if [u, v] != candidate1 and not union(u, v):
                    return candidate1
            return candidate2
        else:  # Cycle case
            for u, v in edges:
                if not union(u, v):
                    return [u, v]

        # Step 5: No redundant edge (shouldn’t happen)
        return []

• Lines 4-14: In-degree: Track nodes with 2 parents, record candidates.
• Lines 17-18: Init: Union-Find setup.
• Lines 21-37: find and union: Standard with path compression and rank.
• Lines 40-49: Process:
• Two parents: Skip candidate1, check cycle, return appropriate edge.
• Cycle only: Return edge causing cycle.
• Time Complexity: O(n * α(n))—near-linear with Union-Find.
• Space Complexity: O(n)—arrays for parent, rank, indegree.

This is like a graph cleaner—track and prune!

Alternative Solution: DFS with Cycle and In-Degree Check

Why an Alternative Approach?

The DFS with cycle and in-degree check approach builds a graph—O(n²) time, O(n) space. It’s more intuitive, tracing paths and checking in-degrees, but slower due to repeated traversals. It’s like walking the graph to spot loops or double parents!

How It Works

Picture this as a graph walker:

• Step 1: Build graph and in-degree array.
• Step 2: DFS for cycle detection:
• Track visited nodes, detect cycles.
• Step 3: Check each edge removal:
• Remove, verify tree (no cycles, one root).
• Step 4: Return last redundant edge.

It’s like a path pruner—trace and cut!

Step-by-Step Example

Example: Same as above

• Step 1: Graph: 1→2, 2→3, 3→1, 4→1, indegree = [0, 2, 1, 1, 0].
• Step 2: DFS from 1: 1→2→3→1 (cycle).
• Step 3: Check removals (reverse order):
• Remove [4, 1]: indegree[1]=1, no cycle, return [4, 1].
• Output: [4, 1].

Code for DFS Approach

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        # Step 1: Build graph and in-degree
        n = len(edges)
        graph = [[] for _ in range(n + 1)]
        indegree = [0] * (n + 1)
        for u, v in edges:
            graph[u].append(v)
            indegree[v] += 1

        # Step 2: DFS for cycle detection
        def has_cycle(graph, node, visited, path):
            visited[node] = True
            path[node] = True
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    if has_cycle(graph, neighbor, visited, path):
                        return True
                elif path[neighbor]:
                    return True
            path[node] = False
            return False

        # Step 3: Check each edge removal
        for i in range(n - 1, -1, -1):
            u, v = edges[i]
            graph[u].remove(v)
            indegree[v] -= 1

            # Verify tree: one root, no cycles
            roots = sum(1 for x in range(1, n + 1) if indegree[x] == 0)
            two_parents = any(x > 1 for x in indegree[1:])
            visited = [False] * (n + 1)
            path = [False] * (n + 1)
            cycle = False
            for start in range(1, n + 1):
                if not visited[start] and has_cycle(graph, start, visited, path):
                    cycle = True
                    break

            if roots == 1 and not two_parents and not cycle:
                return [u, v]

            graph[u].append(v)
            indegree[v] += 1

        # Step 4: No redundant edge (shouldn’t happen)
        return []

• Lines 4-10: Build: Graph and in-degree.
• Lines 13-23: has_cycle: DFS for cycle detection.
• Lines 26-46: Check: Remove edge, verify tree properties, return if valid.
• Time Complexity: O(n²)—n edges, O(n) DFS each.
• Space Complexity: O(n)—graph and arrays.

It’s a graph cleaner—trace and prune!

Comparing the Two Solutions

• Union-Find (Best):
• Pros: O(n * α(n)) time, O(n) space, near-linear.
• Cons: Union-Find less intuitive.
• DFS (Alternative):
• Pros: O(n²) time, O(n) space, clear path tracing.
• Cons: Slower, more complex.

Union-Find wins for efficiency.

Additional Examples and Edge Cases

• Input: edges = [[1, 2], [2, 1]]
• Output: [2, 1].
• Input: edges = [[1, 2], [2, 3], [3, 1]]
• Output: [3, 1].

Union-Find handles these well.

Complexity Breakdown

• Union-Find: Time O(n * α(n)), Space O(n).
• DFS: Time O(n²), Space O(n).

Union-Find is optimal.

Key Takeaways

• Union-Find: Set pruning—smart!
• DFS: Path checking—clear!
• Graphs: Untangling is fun.
• Python Tip: Union-Find rocks—see Python Basics.

Final Thoughts: Prune That Graph

LeetCode 685: Redundant Connection II in Python is a fun graph challenge. Union-Find with in-degree tracking offers speed and elegance, while DFS provides a clear alternative. Want more? Try LeetCode 684: Redundant Connection or LeetCode 547: Number of Provinces. Ready to untangle? Head to Solve LeetCode 685 on LeetCode and fix that network today!