Connected

Q : A is reachable from B?

Union Find - A and B are the same set?

399. Evaluate Division

DFS

class Solution(object):
    def calcEquation(self, equations, values, queries):
        n = len(values)
        self.graph = collections.defaultdict(dict)
        for i in xrange(n):
            c1, c2 = equations[i]
            self.graph[c1][c2] = values[i]
            self.graph[c2][c1] = 1.0/values[i]

        res = []
        for f, t in queries:
            ret = [-1.0]
            self.dfs(f, t, set(), 1.0, ret)
            res.append(ret[0])
        return res

    def dfs(self, start, end, visited, path, ret):
        graph = self.graph
        if start == end and (start in graph):
            ret[0] = path
            return 

        if start in visited:
            return

        visited.add(start)

        for nei in graph[start].keys():
            self.dfs(nei, end, visited, path * graph[start][nei], ret)