python solution as graph dfs


  • 0
    R
    class Solution(object):
    	def path(self, G, A, u, v, visited, S):
    		if (u,v) in G: return S * G[(u,v)]
    		if u == v: return S
    		visited.add(u)
    		for w in A[u]:
    			if w not in visited:
    				c = self.path(G, A, w, v, visited, S * G[(u, w)])
    				if c != -1: return c
    		return -1
    		
    	def calcEquation(self, equations, values, query):
    		E = set()
    		V = set()
    		for i in range(len(equations)):
    			e = equations[i]
    			v = values[i]
    			E.add((e[0],e[1],v))
    			E.add((e[1],e[0],1.0/v))
    			V.add(e[0])
    			V.add(e[1])
    			pass
    		
    		G = {}
    		A = {}
    		for v in V:
    			G[(v,v)] = 1.0
    			A[v] = set([v])
    		for u in E:
    			G[(u[0],u[1])] = u[2]
    			for v in E:
    				if u == v: continue
    				if u[1] == v[0]:
    					G[(u[0],v[1])] = u[2] * v[2]
    					A[u[0]].add(v[1])
    					A[u[1]].add(v[0])
    				if u[0] == v[1]:
    					G[(v[0],u[1])] = u[2] * v[2]
    					A[v[0]].add(u[1])
    					A[v[1]].add(u[0])
    		ans = []
    		for q in query:
    			if q[0] not in V or q[1] not in V:
    				r = -1
    			else:
    				r = self.path(G, A, q[0], q[1], set(),1)
    			ans.append(r)
    		
    		return ans
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.