###### tags: `Leetcode` `medium` `graph` `bfs` `python` `c++`

# 399. Evaluate Division

## [題目連結:] https://leetcode.com/problems/evaluate-division/

## 題目:
You are given an array of variable pairs ```equations``` and an array of real numbers ```values```, where ```equations[i] = [Ai, Bi]``` and ```values[i]``` represent the equation ```Ai / Bi = values[i]```. Each ```Ai``` or ```Bi``` is a string that represents a single variable.

You are also given some ```queries```, where ```queries[j] = [Cj, Dj]``` represents the ```jth``` query where you must find the answer for ```Cj / Dj = ?```.

Return the answers to all queries. If a single answer cannot be determined, return ```-1.0```.

**Note:** The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

**Example 1:**

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]

**Example 2:**

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

**Example 3:**

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

## 解題想法:
* 此題為:
* equations=[['a','b']], values=[0.5]
* 表示**a/b**=0.5
* queries=['b','a'],表示欲求**b/a**??
* 若queries中出現equations未出現的字母則return -1
* 使用圖解:
* **Step1**: 建立有向邊
* equations=[['x','y']],values=[v]
* case1: **x/y=v** 圖為**x->[y,v]**
* case2: **y/x=1/v** 圖為**y->[x,1/v]**

	edge=defaultdict(list)
	#建立有向邊
	for i in range(len(equations)):
		x,y = equations[i]
		v = values[i]
		edge[x].append([y,v])       #x->y 即 x/y=v
		edge[y].append([x,1.0/v])   #y->x 即 y/x =1/v

* **Step2**: 計算互相有關係點為連通分量
* init:
* clusters=[] :存連通分量集合
* visit=set() :查看是否已經拜訪過此點
* **找個特定點，求其他點與他的關係**

	for x,y in equations:
		map={} #存當前數到某特定點的關係
		if x not in visit:
			start=x #若該點沒遍歷過 就已他為特定點
			visit.add(start) #set用add remove
			map[start]=1 #自己除自己為1
			#用bfs遍歷 該點為首到其他點的相除值
			head=[start]
			while head:
				cur=head.pop()
				for node,val in edge[cur]: #找其鄰居
					if node not in visit:
						visit.add(node)
						head.append(node)
						#計算start與該點的相除關係: start/該點
						map[node]=map[cur]*val
		clusters.append(map)
	'''
	ex: equations = [["a","b"],["b","c"]] 
	    values = [2.0,3.0]
	  2      3		
	a---->b---->c
	  1/2   1/3
	  
	clusters=[{'a': 1, 'b': 2.0, 'c': 6.0}, {}]
	為a的視角除其他人: {'a': 1, 'b': 2.0, 'c': 6.0}
	'''

* **Step3**: 求queries的組合
* 其中: **res.append(case[y]/case[x])**
* 要相反!!!!
* ex: 求["a","c"], x='a',y='c'
* case中: {'a': 1, 'b': 2.0, 'c': 6.0}
* case中的'a'、'c'為，a/a=1, a/c=6
* 所以求a/c為 case['c']/case['a']= 6/1=6

	res=[]
	for x,y in queries:
		haveRes=False
		for case in clusters:
			if x in case and y in case:
				res.append(case[y]/case[x])
				haveRes=True
				break
		if not haveRes:
			res.append(-1)

## Python:

from collections import defaultdict
class Solution(object):
    def calcEquation(self, equations, values, queries):
        """
        :type equations: List[List[str]]
        :type values: List[float]
        :type queries: List[List[str]]
        :rtype: List[float]
        """
        edge=defaultdict(list)
        #建立有向邊
        for i in range(len(equations)):
            x,y = equations[i]
            v = values[i]
            edge[x].append([y,v])       #x->y 即 x/y=v
            edge[y].append([x,1.0/v])   #y->x 即 y/x =1/v
        clusters=[] #存連通分量集合
        #visit查看是否已拜訪過此點
        visit = set() #用set 主要為集合不會包含重複值
        #計算互相有關係點為連通分量
        #找個特定點 求其他點與他的關係
        for x,y in equations:
            map={} #存當前數到某特定點的關係
            if x not in visit:
                start=x #若該點沒遍歷過 就已他為特定點
                visit.add(start) #set用add remove
                map[start]=1 #自己除自己為1
                #用bfs遍歷 該點為首到其他點的相除值
                head=[start]
                while head:
                    cur=head.pop()
                    for node,val in edge[cur]: #找其鄰居
                        if node not in visit:
                            visit.add(node)
                            head.append(node)
                            #計算start與該點的相除關係: start/該點
                            map[node]=map[cur]*val
            clusters.append(map)
        #print(clusters)
        #[{'a': 1, 'b': 2.0, 'c': 6.0}, {}]
        #print('為a的視角除其他人:',clusters[0])
        #為a的視角除其他人: {'a': 1, 'b': 2.0, 'c': 6.0}
        res=[]
        for x,y in queries:
            haveRes=False
            for case in clusters:
                if x in case and y in case:
                    #要相反!!!! ex: case存的 'b':2.0 是指 a/b = 2.0 
                    #所以求b/a 要用case[b]/case[a]
                    #ex: 求["a","c"], x='a',y='c'
                    #case中: {'a': 1, 'b': 2.0, 'c': 6.0}
                    #case中的'a'、'c'為，a/a=1, a/c=6
                    #所以求a/c為 case['c']/case['a']= 6/1=6
                    res.append(case[y]/case[x])
                    haveRes=True
                    break
            if not haveRes:
                res.append(-1)
        return res

equations = [["a","b"],["b","c"]] 
values = [2.0,3.0]
queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]

result = Solution()
ans=result.calcEquation(equations,values,queries)
print(ans)

## C++:
* 寫的超亂請見諒

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string, vector<pair<string, double>>> graph;
        //connect the graph
        for (int i=0; i<equations.size(); i++){
            string x=equations[i][0], y=equations[i][1];
            double v=values[i];
            graph[x].push_back(pair(y,v));
            graph[y].push_back(pair(x,double(1/v)));
        }
        vector<unordered_map<string, double>> clusters;
        unordered_set<string> visited;
        //find the clusters in the graph
        for (int i=0; i<equations.size(); i++){
            unordered_map<string, double> map;
            string x=equations[i][0], y=equations[i][1];
            if (visited.find(x)==visited.end()){
                visited.insert(x);
                map[x]=1; // x/x=1
                queue<string> que;
                que.push(x);
                while (!que.empty()){
                    string cur=que.front(); que.pop();
                    for (auto &neighber: graph[cur]){
                        if (visited.find(neighber.first)==visited.end()){
                            visited.insert(neighber.first);
                            que.push(neighber.first);
                            map[neighber.first]=map[cur]*neighber.second;
                        }
                    }
                }
                clusters.push_back(map);
            }
        }
        //get the res
        vector<double> res;
        for (int i=0; i<queries.size(); i++){
            string x=queries[i][0], y=queries[i][1];
            bool haveRes=false;
            for (auto& clusterMap: clusters){
                if ((clusterMap.find(x)!=clusterMap.end()) && (clusterMap.find(y)!=clusterMap.end())){
                    res.push_back(clusterMap[y]/clusterMap[x]);
                    haveRes=true;
                    break;
                }
            }
            if (!haveRes)
                res.push_back(-1);
        }
        return res;
    }
};