684. Redundant Connection

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/redundant-connection
• topics: Graph, Union Find

Description

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to 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 graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

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 input.

Idea

• Start from leafs and remove nodes that have only 1 connection
• Union find - faster

Code

Remove leafs

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        adj = defaultdict(set)
 
        for a, b in edges:
            adj[a].add(b)
            adj[b].add(a)
 
        # Start from leafs and remove nodes that have only 1 connection
        d = deque(node for node in adj if len(adj[node]) == 1)
        while d:
            node = d.popleft()
            for neighbor in adj[node]:
                adj[neighbor].remove(node)
                if len(adj[neighbor]) == 1:
                    d.append(neighbor)
            del adj[node] 
 
        # Find the last redundant connection
        for a, b in reversed(edges):
            if a in adj and b in adj and b in adj[a]:
                return [a, b]

Union find

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        root = list(range(len(edges) + 1)) # each node is root of own subtree
 
        def find_root(node):
            if root[node] != node:
                root[node] = find_root(root[node]) # set root for node as root of subtree
            return root[node] # found root of subtree
 
        for node1, node2 in edges: 
            root1, root2 = find_root(node1), find_root(node2)
 
            if root1 == root2:
                return [node1, node2] # both nodes are already in same subtree
 
            root[root2] = root1 # found new connection between nodes / subtrees
            # root[root1] = root2 also works