Leetcode 684. Redundant Connection

Problem

Leetcode 684 - Redundant Connection

Example:

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

Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]

Approach

For a graph to have a cycle, every node must have 2 or more neighbors, thus we can use tropological sort to get all the neighbor counts(indegree counts) then if indegree == 1, we can disconnect them first. Once we’re all done with the process of disconnecting the 1 neighbor edge, we can loop through the edges.

If the indgree count is == 2, and the adjacent indegree count exists, then we can return that edge.

Here is the Python code for the solution:

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        indegree = [0] * (n+1)
        adj = [[] for _ in range(n+1)]

        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
            indegree[u] += 1
            indegree[v] += 1
        
        q = deque()
        for i in range(1, n+1):
            if indegree[i] == 1:
                q.append(i)

        while q:
            node = q.popleft()

            indegree[node] -= 1
            for i in adj[node]:
                indegree[i] -= 1
                if indegree[i] == 1:
                    q.append(i)
        
        for u, v in reversed(edges):
            if indegree[u] == 2 and indegree[v]:
                return [u, v]
        
        return []    

Time Complexity and Space Complexity

Time Complexity: $O(V + E)$

Space Complexity: $O(V + E)$