Redundant Connection

https://leetcode.com/problems/redundant-connection/description/

1. DFS

For each (c, v) edge, traverse DFS to find if we can connect c to v. If so , it must be a duplicate edge.

from collections import defaultdict

class Solution(object):
    def findRedundantConnection(self, edges):
        """
        :type edges: List[List[int]]
        :rtype: List[int]
        """

        graph = defaultdict(set)
        visited = {}

        def dfs(source, target):
            if not source in visited:
                visited[source] = True

                if source == target:
                    return True

                for tmp in graph[source]:
                    if dfs(tmp, target):
                        return True

            return False


        for s, v in edges:
            visited = {}
            if s in graph and v in graph and dfs(s,v):
                return [s, v]

            graph[s].add(v)
            graph[v].add(s)