5400. Destination City

You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBi. Return the destination city, that is, the city without any path outgoing to another city.

It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.

Example 1:

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo" 
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

Example 2:

Input: paths = [["B","C"],["D","B"],["C","A"]]
Output: "A"
Explanation: All possible trips are: 
"D" -> "B" -> "C" -> "A". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
Clearly the destination city is "A".

Example 3:

Input: paths = [["A","Z"]]
Output: "Z"

Constraints:

• 1 <= paths.length <= 100
• paths[i].length == 2
• 1 <= cityAi.length, cityBi.length <= 10
• cityAi != cityBi
• All strings consist of lowercase and uppercase English letters and the space character.

---

给定一个路径数组，每条路径标明了出发城市和到达城市，问所有路径最终会到达哪个城市，最终到达的城市是只有进路，没有出路的城市。

简单题，统计下所有城市的入度和出度，出度为0的城市即为最终城市。

class Solution {
public:
	string destCity(vector<vector<string>>& paths) {
		map<string, pair<int,int>> count;
		for (int i = 0; i < paths.size(); ++i) {
			string src = paths[i][0], dest = paths[i][1];
			++count[src].first; // 出度
			++count[dest].second; // 入度
		}
		for (map<string, pair<int, int>>::iterator it = count.begin(); it != count.end(); ++it) {
			if (it->second.first == 0) {
				return it->first;
			}
		}
		return "";
	}
};

本代码提交AC，用时56MS。