4 ms java O(v+e+n) solution


  • 0
    H

    DFS on all connected component of the graph, use the root of the dfs spinning tree as an intermediate node when calculating the ratio between two nodes. correct me if I'm wrong about the time complexity. n: the number of queries.

        class Node{
            String name;
            List<Node> adjs = new ArrayList<>();
            List<Double> adjsDiv = new ArrayList<>();
            Node root;//root in the search spinning tree
            double divRoot = 0.0; // ?
            public Node(String name){
                this.name = name;
            }
        }
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            int n = equations.length;
            int m = queries.length;
            HashMap<String, Node> graph = new HashMap<>();
            for(int i=0; i<n; i++){
                String uName = equations[i][0];
                String vName = equations[i][1];
                double uDevideV = values[i];
                Node uNode = graph.get(uName);
                if(uNode == null){
                    uNode = new Node(uName);
                    graph.put(uName, uNode);
                }
                Node vNode = graph.get(vName);
                if(vNode == null){
                    vNode = new Node(vName);
                    graph.put(vName, vNode);
                }
                uNode.adjs.add(vNode);
                uNode.adjsDiv.add(uDevideV);
                vNode.adjs.add(uNode);
                vNode.adjsDiv.add(1.0/uDevideV);
            }
            HashSet<Node> visited = new HashSet<>();
            for(Node node : graph.values()){
                dfs(1.0, node, node, graph, visited);
            }
            double[] ans = new double[m];
            for(int i=0; i<m; i++){
                String u = queries[i][0];
                String v = queries[i][1];
                Node uNode = graph.get(u);
                Node vNode = graph.get(v);
                if(uNode == null || vNode == null || uNode.root != vNode.root){
                    ans[i] = -1.0;
                    continue;
                }
                ans[i] = uNode.divRoot/vNode.divRoot;
            }
            return ans;
        }
        
        private void dfs(double rootDiv, Node root, Node curr, HashMap<String, Node> graph, HashSet<Node> visited){
            if(visited.contains(curr)) return;
            curr.root = root;
            curr.divRoot = 1.0/rootDiv;
            visited.add(curr);
            for(int i=0; i<curr.adjs.size(); i++){
                Node next = curr.adjs.get(i);
                double currDivNext = curr.adjsDiv.get(i);
                dfs(rootDiv*currDivNext, root, next, graph, visited);
            }
        }
    

Log in to reply
 

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