Directed Graph

Algorithms
graph
Catalogue
  1. 1. 399. Evaluate Division
    1. 1.1. Follow up
  2. 2. 332. Reconstruct Itinerary

399. Evaluate Division

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def calcEquation(self, equations, values, queries):
        graph = collections.defaultdict(dict)
        n = len(equations)
        for i in range(n):
            src, dst = equations[i]
            graph[src][dst] = values[i]
            graph[dst][src] = 1.0 / values[i]

        ans = []
        for start, end in queries:
            self.res = -1.0
            self.dfs(start, end, set(), 1.0, graph)
            ans.append(self.res)
        return ans

    def dfs(self, start, end, visited, path, graph):
        if start == end and start in graph:
            self.res = 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], graph)

Time Analysis

  • Construct the Graph O(Edges), numbers of equations
  • Query, O(Edges)

Follow up

  1. Follow up1: if there are different path from start node to end node ?
  • calcaulate the lowest and highest exchange rate
  1. Follow up2: if we have many queries, how to speed up queries?
  • use hash table to save the results
  • add connected line in the graph!

332. Reconstruct Itinerary

  • DFS post order traversal!
  • a little like topological sort, but different dependency!!!
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def findItinerary(self, tickets):
        graph = collections.defaultdict(list)
        for f, t in sorted(tickets, reverse = True):
            graph[f].append(t)

        res = []
        def dfs(node):
            while graph[node]:
                dfs(graph[node].pop())
            res.append(node)
        dfs('JFK')
        return res[::-1]
Share