-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathEvaluate Division.js
More file actions
41 lines (31 loc) · 950 Bytes
/
Evaluate Division.js
File metadata and controls
41 lines (31 loc) · 950 Bytes
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
29
30
31
32
33
34
35
36
37
38
39
40
41
var calcEquation = function(equations, values, queries) {
let graph = {};
for (let i = 0; i < equations.length; i++) {
let [a, b] = equations[i];
let val = values[i];
if (!graph[a]) graph[a] = [];
if (!graph[b]) graph[b] = [];
graph[a].push([b, val]);
graph[b].push([a, 1 / val]);
}
function dfs(src, dest, visited) {
if (!(src in graph)) return -1.0;
if (src === dest) return 1.0;
visited.add(src);
for (let [next, weight] of graph[src]) {
if (!visited.has(next)) {
let res = dfs(next, dest, visited);
if (res !== -1.0) {
return res * weight;
}
}
}
return -1.0;
}
let result = [];
for (let [src, dest] of queries) {
let visited = new Set();
result.push(dfs(src, dest, visited));
}
return result;
};