@@ -10,65 +10,64 @@ public class _399 {
1010
1111public static class Solution1 {
1212/**
13- * Credit: https://discuss.leetcode.com/topic/59146/java-ac-solution-using-graph
14- * <p>
15- * Image a/b = k as a link between node a and b, the weight from a to b is k, the reverse link
16- * is 1/k. Query is to find a path between two nodes.
13+ * Credit: https://medium.com/@null00/leetcode-evaluate-division-52a0158488c1
1714 */
18- public double []calcEquation (String [][]equations ,double []values ,String [][]queries ) {
19- Map <String ,List <String >>pairs =new HashMap <>();
20- Map <String ,List <Double >>valuePairs =new HashMap <>();
21- for (int i =0 ;i <equations .length ;i ++) {
22- String []equation =equations [i ];
23- if (!pairs .containsKey (equation [0 ])) {
24- pairs .put (equation [0 ],new ArrayList <>());
25- valuePairs .put (equation [0 ],new ArrayList <>());
26- }
27- if (!pairs .containsKey (equation [1 ])) {
28- pairs .put (equation [1 ],new ArrayList <>());
29- valuePairs .put (equation [1 ],new ArrayList <>());
30- }
31- pairs .get (equation [0 ]).add (equation [1 ]);
32- pairs .get (equation [1 ]).add (equation [0 ]);
33- valuePairs .get (equation [0 ]).add (values [i ]);
34- valuePairs .get (equation [1 ]).add (1 /values [i ]);
35- }
15+ private Map <String ,String >root ;
16+ private Map <String ,Double >rate ;
3617
37- double []result =new double [queries .length ];
38- for (int i =0 ;i <queries .length ;i ++) {
39- String []query =queries [i ];
40- result [i ] =dfs (query [0 ],query [1 ],pairs ,valuePairs ,new HashSet <>(),1.0 );
41- if (result [i ] ==0.0 ) {
42- result [i ] = -1.0 ;
43- }
44- }
45- return result ;
18+ public double []calcEquation (List <List <String >>equations ,double []values ,List <List <String >>queries ) {
19+ root =new HashMap <String ,String >();
20+ rate =new HashMap <String ,Double >();
21+ int n =equations .size ();
22+ for (int i =0 ;i <n ; ++i ) {
23+ String X =equations .get (i ).get (0 );
24+ String Y =equations .get (i ).get (1 );
25+ root .put (X ,X );
26+ root .put (Y ,Y );
27+ rate .put (X ,1.0 );
28+ rate .put (Y ,1.0 );
4629 }
4730
48- private double dfs (String start ,String end ,Map <String ,List <String >>pairs ,
49- Map <String ,List <Double >>valuePairs ,HashSet <String >set ,double value ) {
50- if (set .contains (start )) {
51- return 0.0 ;
52- }
53- if (!pairs .containsKey (start )) {
54- return 0.0 ;
55- }
56- if (start .equals (end )) {
57- return value ;
58- }
59- set .add (start );
31+ for (int i =0 ;i <n ; ++i ) {
32+ String X =equations .get (i ).get (0 );
33+ String Y =equations .get (i ).get (1 );
34+ union (X ,Y ,values [i ]);
35+ }
6036
61- List <String >stringList =pairs .get (start );
62- List <Double >valueList =valuePairs .get (start );
63- double tmp =0.0 ;
64- for (int i =0 ;i <stringList .size ();i ++) {
65- tmp =dfs (stringList .get (i ),end ,pairs ,valuePairs ,set ,value *valueList .get (i ));
66- if (tmp !=0.0 ) {
67- break ;
68- }
37+ double []result =new double [queries .size ()];
38+ for (int i =0 ;i <queries .size (); ++i ) {
39+ String X =queries .get (i ).get (0 );
40+ String Y =queries .get (i ).get (1 );
41+ if (!root .containsKey (X ) || !root .containsKey (Y )) {
42+ result [i ] = -1 ;
43+ continue ;
6944 }
70- set .remove (start );
71- return tmp ;
45+
46+ String rootx =findRoot (X ,X ,1.0 );
47+ String rooty =findRoot (Y ,Y ,1.0 );
48+ result [i ] =rootx .equals (rooty ) ?rate .get (X ) /rate .get (Y ) : -1.0 ;
7249 }
50+
51+ return result ;
52+ }
53+
54+ private void union (String X ,String Y ,double v ) {
55+ String rootx =findRoot (X ,X ,1.0 );
56+ String rooty =findRoot (Y ,Y ,1.0 );
57+ root .put (rootx ,rooty );
58+ double r1 =rate .get (X );
59+ double r2 =rate .get (Y );
60+ rate .put (rootx ,v *r2 /r1 );
61+ }
62+
63+ private String findRoot (String originalX ,String X ,double r ) {
64+ if (root .get (X ).equals (X )) {
65+ root .put (originalX ,X );
66+ rate .put (originalX ,r *rate .get (X ));
67+ return X ;
68+ }
69+
70+ return findRoot (originalX ,root .get (X ),r *rate .get (X ));
71+ }
7372 }
7473}