AC Java Graph + DFS


  • 0
    S

    Accepted Java code using Graph + DFS

    	private class Node{
    		private Map<String, Double> nextNodes;
    		private boolean isVisit;
    		private Node(){
    			this.nextNodes = new HashMap<String, Double>();
    			this.isVisit = false;
    		}
    	}
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            if(equations.length == 0) return null;
            double[] res = new double[queries.length];
            Map<String, Node> graph = new HashMap<String, Node>();
            for(int i = 0; i < equations.length; i++){
            	if(!graph.containsKey(equations[i][0])) graph.put(equations[i][0], new Node());
            	graph.get(equations[i][0]).nextNodes.put(equations[i][1], values[i]);
            	if(!graph.containsKey(equations[i][1])) graph.put(equations[i][1], new Node());
            	graph.get(equations[i][1]).nextNodes.put(equations[i][0], 1 / values[i]);
            }
            for(int i = 0; i < queries.length; i++){
            	if(!graph.containsKey(queries[i][0]) || !graph.containsKey(queries[i][1])) res[i] = -1.0;
            	else if(queries[i][0].equals(queries[i][1])) res[i] = 1.0;
            	else res[i] = dfs(queries[i][0], queries[i][1], graph);
                for(String nd : graph.keySet()){
                	graph.get(nd).isVisit = false;
                }
            }
            return res;
        }
        public double dfs(String start, String end, Map<String, Node> graph){
        	Stack<Node> stk = new Stack<Node>();
        	Stack<Double> valStk = new Stack<Double>();
        	stk.push(graph.get(start));
        	valStk.push(1.0);
        	while(!stk.isEmpty()){
        		Node nd = stk.pop();
        		double val = valStk.pop();
        		nd.isVisit = true;
        		for(String key : nd.nextNodes.keySet()){
        			if(key.equals(end)) return val *= nd.nextNodes.get(key);
        			else {
        				if(!graph.get(key).isVisit){
        					stk.push(graph.get(key));
        					valStk.push(val * nd.nextNodes.get(key));
        				}
        			}
        		}
        	}
        	return -1.0;
        }
    

Log in to reply
 

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