给出一堆equations和values，其中的值代表A_i/B_i=values_i，给出一堆问询，输出每个queries_i_1/queries_i_2的值
思路一：建图，BFS
思路二：并查集，写法参考了Discussion
1 #399
2 #Runtime: 25 ms (Beats 11.39%)
3 #Memory: 13.4 MB (Beats 73.42%)
4
5 class Solution(object):
6 def calcEquation(self, equations, values, queries):
7 """
8 :type equations: List[List[str]]
9 :type values: List[float]
10 :type queries: List[List[str]]
11 :rtype: List[float]
12 """
13 equ = {}
14
15 def find(x):
16 p, v = equ.setdefault(x, (x, 1))
17 if x != p:
18 r, w = find(p)
19 equ[x] = (r, w * v)
20 return equ[x]
21
22 def union(x, y, v):
23 px, pv = find(x)
24 py, pw = find(y)
25 if not v:
26 if px == py:
27 return pv / pw
28 else:
29 return -1
30 if px != py:
31 equ[px] = (py, pw / pv * v)
32
33 for (x, y), v in zip(equations, values):
34 union(x, y ,v)
35 ans = []
36 for x, y in queries:
37 if x in equ and y in equ:
38 ans.append(union(x, y, 0))
39 else:
40 ans.append(-1)
41 return ans
42