_684. Redundant Connection.md

684. Redundant Connection

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : January 29, 2025

Last updated : January 29, 2025

---

Related Topics : Depth-First Search, Breadth-First Search, Union Find, Graph

Acceptance Rate : 66.09 %

---

Plan:

• Make edge set for each node
• Choose a random start node for traversal (default to $1$ since nodes are labelled $1-n$ inclusive)
• DFS from start
  • If an end node is encountered, return None
  • If a visited node is encountered, return the path from the first time visiting that node till the current
• Return the last edge pair in edges where both $u$ and $v$ appear in the outputed cycle path

Reasoning:

• If we have a connected graph with $n$ edges, then there must be a SINGLE cycle
• Removing any of those edges is valid
• Parameters dictate to give the last edge of the input edge list that fulfills the condition

---

Solutions

• m684.py

Python

m684.py

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        edges_n = defaultdict(set)
        for u, v in edges :
            edges_n[u].add(v)
            edges_n[v].add(u)


        # return nodes that are in the graph's cycle
        def dfs_find_cycle_nodes(curr: int, 
                                 prev: int, 
                                 stk: List[int], 
                                 visited: Set[int], 
                                 edges: defaultdict) -> List[int] :
            if curr in visited :
                return stk[stk.index(curr):]
            visited.add(curr)
            stk.append(curr)

            for nxt in edges[curr] :
                if nxt == prev :
                    continue

                output = dfs_find_cycle_nodes(nxt, curr, stk, visited, edges)
                if output :
                    return output

            visited.remove(curr)
            stk.pop()
            return None

        cycle_edges = set(dfs_find_cycle_nodes(1, None, [], set(), edges_n))

        for u, v in reversed(edges) :
            if u in cycle_edges and v in cycle_edges :
                return [u, v]

        return None