Tag Archives: 图论

LeetCode Clone Graph

LeetCode Clone Graph
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:Nodes are labeled uniquely.We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.

  1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
  2. Second node is labeled as 1. Connect node 1 to node 2.
  3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

给定一个无向图,要求克隆一个一样的图,也就是深拷贝。
图的问题,想到应该是DFS或者BFS,但是没太想明白,因为DFS过程中可能遇到之前已经new过的节点,不知道怎么判断比较好,查看讨论区,发现每new一个节点,把这个节点存到一个hash表中就好了,下回先查hash表,不中才new新的。
因为每个节点的label是unique的,所以hash的key可以是label,value是node*。
完整代码如下,注意第9行,new出来的节点要先加入hash,再递归DFS,否则递归DFS在hash表中找不到当前的节点,比如{0,0,0}这个样例就会出错。

class Solution {
private:
	unordered_map<int, UndirectedGraphNode*> graph;
public:
	UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
		if (node == NULL)return NULL;
		if (graph.find(node->label) != graph.end())return graph[node->label];
		UndirectedGraphNode *cur = new UndirectedGraphNode(node->label);
		graph[cur->label] = cur;
		for (auto& n : node->neighbors) {
			cur->neighbors.push_back(cloneGraph(n));
		}
		return cur;
	}
};

本代码提交AC,用时26MS。

LeetCode Pacific Atlantic Water Flow

LeetCode Pacific Atlantic Water Flow
Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.
Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.
Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.
Note:

  1. The order of returned grid coordinates does not matter.
  2. Both m and n are less than 150.

Example:

Given the following 5x5 matrix:
  Pacific ~   ~   ~   ~   ~
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * Atlantic
Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

给定一个矩阵,每个元素表示一个方格中水柱的高度,左上角是太平洋,右下角是大西洋,问哪些坐标的水柱既能流向太平洋,又能流向大西洋。注意每个水柱能流向和它同样高或者比它第的地方。
一看就是DFS或者BFS的题。
拍脑袋解法。对于每个坐标,我们DFS看能否分别到达太平洋或者大西洋。代码如下:

vector<vector<int>> dirs = { { 0,-1 },{ -1,0 },{ 0,1 },{ 1,0 } }; // 0:left, 1:up, 2:right, 3:down
class Solution4 {
private:
	int m, n;
	bool isOk(int x, int y) {
		return x >= 0 && x < m&&y >= 0 && y < n;
	}
	// type=0:Pacific; 1:Atlantic
	bool dfs(vector<vector<int>>& matrix, vector<vector<int>>& visited, int x, int y, const int& type) {
		for (int i = 0; i < dirs.size(); ++i) {
			int xx = x + dirs[i][0], yy = y + dirs[i][1];
			if (isOk(xx, yy) && visited[xx][yy] == 0 && matrix[x][y] >= matrix[xx][yy]) {
				visited[xx][yy] = 1;
				if (dfs(matrix, visited, xx, yy, type)) {
					visited[xx][yy] = 0;
					return true;
				}
				visited[xx][yy] = 0;
			}
			else if ((type == 0 && (xx < 0 || yy < 0)) || (type == 1 && (xx >= m || yy >= n))) {
				return true;
			}
		}
		return false;
	}
public:
	vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
		if (matrix.empty() || matrix[0].empty())return{};
		m = matrix.size(), n = matrix[0].size();
		vector<vector<int>> visited(m, vector<int>(n, 0));
		vector<pair<int, int>> ans;
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				visited[i][j] = 1;
				if (dfs(matrix,visited,i,j,0)&&dfs(matrix,visited,i,j,1))
					ans.push_back(pair<int, int>(i, j));
				visited[i][j] = 0;
			}
		}
		return ans;
	}
};

本代码提交AC,用时702MS。
这种DFS的解法重复计算非常多,比如(a,b)这个点DFS时会经过(a-1,b-1),而(a-1,b-1)之前其实已经DFS过了。可以在DFS的过程中记录下经过的点的DFS状态,比如在DFS(a,b)时,走到(a-1,b-1),先查状态,发现(a-1,b-1)到不了大西洋,那现在这条路就没必要继续DFS下去了;相反,如果查状态发现(a-1,b-1)能到大西洋,则后续不需要再DFS其他路径了。
保存状态的DFS版本如下:

vector<vector<int>> dirs = { { 0,-1 },{ -1,0 },{ 0,1 },{ 1,0 } }; // 0:left, 1:up, 2:right, 3:down
// memory version
class Solution3 {
private:
	int m, n;
	bool isOk(int x, int y) {
		return x >= 0 && x < m&&y >= 0 && y < n;
	}
	bool dfs(vector<vector<int>>& matrix, vector<vector<int>>& visited, int x, int y, const int& type, vector<vector<vector<int>>>& mem) {
		for (int i = 0; i < dirs.size(); ++i) {
			int xx = x + dirs[i][0], yy = y + dirs[i][1];
			if (isOk(xx, yy) && visited[xx][yy] == 0 && matrix[x][y] >= matrix[xx][yy]) {
				if (mem[xx][yy][type] == 1) {
					mem[x][y][type] = 1;
					return true;
				}
				else if (mem[xx][yy][type] == 0)continue;
				visited[xx][yy] = 1;
				if (dfs(matrix, visited, xx, yy, type, mem)) {
					mem[x][y][type] = 1;
					visited[xx][yy] = 0;
					return true;
				}
				visited[xx][yy] = 0;
			}
			else if ((type == 0 && (xx < 0 || yy < 0)) || (type == 1 && (xx >= m || yy >= n))) {
				mem[x][y][type] = 1;
				return true;
			}
		}
		mem[x][y][type] = 0;
		return false;
	}
public:
	vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
		if (matrix.empty() || matrix[0].empty())return{};
		m = matrix.size(), n = matrix[0].size();
		vector<vector<int>> visited(m, vector<int>(n, 0));
		vector<vector<vector<int>>> mem(m, vector<vector<int>>(n, vector<int>(2, -1)));
		vector<pair<int, int>> ans;
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				visited[i][j] = 1;
				if (mem[i][j][0] == -1)
					dfs(matrix, visited, i, j, 0, mem);
				if (mem[i][j][1] == -1)
					dfs(matrix, visited, i, j, 1, mem);
				visited[i][j] = 0;
				if (mem[i][j][0] == 1 && mem[i][j][1] == 1)
					ans.push_back(pair<int, int>(i, j));
			}
		}
		return ans;
	}
};

无奈,在第112/113这个数据上WA了,但是这个数据太大了,面对的是汪洋大海,调试太费劲,暂时没fix bug。
看了下讨论区,发现主流解法是从海洋开始BFS,分别从大西洋和太平洋BFS,记录下两个海洋分别能访问到的点,最后如果某个点同时被两个海洋访问到了,则说明该点既能到达大西洋,也能到达太平洋。
代码如下:

vector<vector<int>> dirs = { { 0,-1 },{ -1,0 },{ 0,1 },{ 1,0 } }; // 0:left, 1:up, 2:right, 3:down
class Solution {
private:
	int m, n;
	bool isOk(int x, int y) {
		return x >= 0 && x < m&&y >= 0 && y < n;
	}
	void bfs(vector<vector<int>>& matrix, queue<pair<int, int>>& Q, vector<vector<int>>& visited) {
		while (!Q.empty()) {
			auto f = Q.front();
			Q.pop();
			visited[f.first][f.second] = 1;
			for (int i = 0; i < dirs.size(); ++i) {
				int x = f.first + dirs[i][0], y = f.second + dirs[i][1];
				if (isOk(x, y) && visited[x][y] == 0 && matrix[f.first][f.second] <= matrix[x][y]) {
					Q.push(pair<int, int>(x, y));
				}
			}
		}
	}
public:
	vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
		if (matrix.empty() || matrix[0].empty())return{};
		m = matrix.size(), n = matrix[0].size();
		vector<vector<int>> pacific(m, vector<int>(n, 0)), atlantic(m, vector<int>(n, 0));
		queue<pair<int, int>> pQ, aQ;
		for (int i = 0; i < m; ++i) { // vertical
			pQ.push(pair<int, int>(i, 0));
			aQ.push(pair<int, int>(i, n - 1));
		}
		for (int i = 0; i < n; ++i) { // horizontal
			pQ.push(pair<int, int>(0, i));
			aQ.push(pair<int, int>(m - 1, i));
		}
		bfs(matrix, pQ, pacific);
		bfs(matrix, aQ, atlantic);
		vector<pair<int, int>> ans;
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				if (pacific[i][j] == 1 && atlantic[i][j] == 1)
					ans.push_back(pair<int, int>(i, j));
			}
		}
		return ans;
	}
};

本代码提交AC,用时减少到45MS。
对于类似的搜索题目,如果是求单个点能否达到目的地,则从起始点或者目的点开始BFS/DFS的效果都是一样的。但是如果要求所有能到达目的点的点,则从目的点开始BFS就能一次性找到这些点,而从每个起始点开始BFS/DFS就非常费劲了。

hihoCoder 1519-逃离迷宫II

hihoCoder 1519-逃离迷宫II

#1519 : 逃离迷宫II

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi被坏女巫抓进里一间有N x M个格子组成的矩阵迷宫。
有些格子是小Hi可以经过的,我们用'.'表示;有些格子上有障碍物小Hi不能经过,我们用'#'表示。小Hi的起始位置用'S'表示,他需要到达用'T'表示的格子才能逃离迷宫。
麻烦的是小Hi被坏女巫施了魔法,他只能选择上下左右某一个方向,沿着这个方向一直走,直到遇到障碍物或者迷宫边界才能改变方向。新的方向可以是上下左右四个方向之一。之后他还是只能沿着新的方向一直走直到再次遇到障碍物或者迷宫边界……
小Hi想知道他最少改变几次方向才能逃离这个迷宫。

输入

第一行包含两个整数N和M。  (1 <= N, M <= 500)
以下N行每行M个字符,代表迷宫。

输出

一个整数代表答案。如果小Hi没法逃离迷宫,输出-1。

样例输入
5 5
S.#.T
.....
.....
.....
.....
样例输出
2

给定一个迷宫,S表示起点,T表示终点,#表示障碍物。行走的时候,只能沿着直线走,直到遇到障碍物或者碰壁,问从S到T,最少需要改变多少次方向。
我一开始是用DFS做的,每次朝一个方向DFS下去,但是因为每次DFS时走了一长条直线,所以回溯的时候需要把之前走过的直线复位。代码如下:

#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<cmath>
using namespace std;
const int MAXN = 505;
int n, m;
int startx, starty, endx, endy;
int ans = INT_MAX;
vector<vector<char>> maze(MAXN, vector<char>(MAXN, '0'));
vector<vector<char>> visited(MAXN, vector<char>(MAXN, '0'));
vector<vector<int>> dirs{ {-1,0},{1,0},{0,-1},{0,1} }; //up,down,left,right
vector<vector<int>> opdirs{ { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }; // 反方向
bool ok(int x, int y) {
	if (x >= 0 && x < n&&y >= 0 && y < m&&maze[x][y] != '#')return true;
	return false;
}
void dfs(int sx,int sy, int step) {
	for (int i = 0; i < 4; ++i) {
		int newx = sx + dirs[i][0], newy = sy + dirs[i][1];
		if (ok(newx, newy) && visited[newx][newy] == '0') {
			visited[newx][newy] = '1';
			bool done = false;
			while (ok(newx, newy)) {
				visited[newx][newy] = '1';
				if (newx == endx&&newy == endy) {
					done = true;
					break;
				}
				newx = newx + dirs[i][0], newy = newy + dirs[i][1];
			}
			if (done) {
				ans = min(ans, step);
			}
			else {
				dfs(newx + opdirs[i][0], newy + opdirs[i][1], step + 1);  // 往回走一步再递归
			}
			while (!(newx == sx&&newy == sy)) {
				if (ok(newx, newy))visited[newx][newy] = '0'; // 复位
				newx = newx + opdirs[i][0], newy = newy + opdirs[i][1];
			}
		}
	}
}
int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	char c;
	for (int i = 0; i < n; ++i) {
		scanf("%c", &c);
		for (int j = 0; j < m; ++j) {
			scanf("%c", &maze[i][j]);
			if (maze[i][j] == 'S') {
				startx = i;
				starty = j;
			}
			else if (maze[i][j] == 'T') {
				endx = i;
				endy = j;
			}
		}
	}
	visited[startx][starty] = '1';
	dfs(startx, starty, 0);
	if (ans == INT_MAX)printf("-1\n");
	else printf("%d\n", ans);
	return 0;
}

本代码提交TLE,很明显会TLE,因为DFS必须把所有方案都走一遍才能得到最小值。
比赛的时候脑子短路,这种搜索问题要求最短XX的肯定用BFS比DFS快呀,因为第一次BFS到的方案肯定就是最优方案呀。只不过这题判断距离用的是转弯次数,以前都是算走过的步数。
对于这题,用BFS也是一样的,BFS的下一个点肯定就是走直线走到无法再走的那个拐角点(cornor)。不过为了防止死循环,要把以前走过的拐角都记录下来,只走那些以前没走过的拐点。
代码如下:

#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<cmath>
#include<queue>
using namespace std;
const int MAXN = 505;
int n, m;
int startx, starty, endx, endy;
typedef struct P {
	int x, y, step;
	P(int x_, int y_, int step_) :x(x_), y(y_), step(step_) {};
};
vector<vector<char>> maze(MAXN, vector<char>(MAXN, '0'));
vector<vector<int>> dirs{ { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } }; //up,down,left,right
vector<vector<int>> opdirs{ { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }; // 反方向
set<int> points;
bool ok(int x, int y) {
	if (x >= 0 && x < n&&y >= 0 && y < m&&maze[x][y] != '#')return true;
	return false;
}
int id(int x, int y) {
	return x*n + y;
}
int bfs() {
	queue<P> q;
	P p(startx, starty, 0);
	q.push(p);
	while (!q.empty()) {
		p = q.front();
		q.pop();
		points.insert(id(p.x, p.y));
		for (int i = 0; i < dirs.size(); ++i) {
			int newx = p.x + dirs[i][0], newy = p.y + dirs[i][1];
			while (ok(newx, newy)) {
				if (newx == endx&&newy == endy) {
					return p.step;
				}
				newx = newx + dirs[i][0], newy = newy + dirs[i][1];
			}
			int cornorx = newx + opdirs[i][0], cornory = newy + opdirs[i][1]; // 往回走一步
			if (points.find(id(cornorx, cornory)) == points.end()) {
				P tmp(cornorx, cornory, p.step + 1);
				q.push(tmp);
			}
		}
	}
	return -1;
}
int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	char c;
	for (int i = 0; i < n; ++i) {
		scanf("%c", &c);
		for (int j = 0; j < m; ++j) {
			scanf("%c", &maze[i][j]);
			if (maze[i][j] == 'S') {
				startx = i;
				starty = j;
			}
			else if (maze[i][j] == 'T') {
				endx = i;
				endy = j;
			}
		}
	}
	printf("%d\n", bfs());
	return 0;
}

本代码提交AC,用时718MS。

LeetCode Minimum Height Trees

LeetCode Minimum Height Trees
For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
Example 1:
Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3

return [1]
Example 2:
Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5

return [3, 4]
Show Hint

    Note:
    (1) According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
    (2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.


    给定一个无向无环图,问以哪个顶点为根形成的有根树的树高是最小的,如果有多个这样的最小高度的有根树,则输出所有这样的根节点。
    很有意思的一题,需要把无向无环图转换为有根树。提示问这样的最小高度的有根树最多有多少个,我想了想,应该最多只有两个吧。可以用反证法,假设有3个,则这3个根肯定会形成环,具体原因大家可以在纸上画个图举个例子就知道了。
    然后我由题目的样例想到的是,把图转换为有根的最小高度的树,根节点应该是从度数最高的前两个节点中选一个。所以我首先统计了所有节点的度数,然后选两个度数最高的节点,对这两个点DFS求以他们为根时的树高,如果树高相同,说明这两个点都是答案,否则取树高更高的节点作为根节点。
    但是很可惜,代码提交之后WA,错误样例是这样的[[0,1],[0,2],[0,3],[2,4],[0,5],[5,6],[6,7],[2,8],[7,9]]。

    8     3
      \    \
        2----0----5----6----7----9
      /    /
    4    1

    在上图中,度数最多的前两个点是0和2,但是转换为有根树的最小高度的树根节点是5。所以我的解法是错误的。
    参考网上的题解,好巧妙呀。这种解法类似于剥洋葱,一层一层把叶子节点剥离掉,最后剩下的2个或者1个节点就是最小树高的根节点。这种解法显然是正确的,没剥掉一层,相当于树高减一,一直减,到最后还剩下的节点肯定就是根节点了。比如上图中,第一层剥掉8,3,9,4,1,变成下图

    2----0----5----6----8

    第二层剥掉之后变成下图

    0----5----6

    第三层剥掉之后就只剩下5号节点了,所以以5号节点为根,树的高度最低,只有3,而我的解法算出来的根节点0的树高是4,不是最小的。

    5

    剥洋葱的解法用BFS来实现就非常方便了,BFS天然就是一层循环就是剥掉一层。
    代码中,初始时,我们把图转换为类似邻接表的结果,但是每个vector里存的是unordered_set,而不是list,因为剥洋葱的时候,比如第一层时剥掉8号节点时,我们同时需要把2号节点的邻接表中的8号节点删掉,所以用unordered_set.erase就非常方便。后面循环时,没剥一层,我们就检查一下,把当前的叶子节点加入到队列中。当剩余的节点数不超过2个时,剩余的节点就是有根树的根节点。如果剩余两个节点,说明这两个节点的高度是一样的,都是正确答案。
    代码如下:

    class Solution {
    public:
    	vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
    		if (n == 1)return{ 0 };
    		int m = edges.size();
    		vector<unordered_set<int>> graph(n, unordered_set<int>());
    		for (int i = 0; i < m; ++i) {
    			graph[edges[i].first].insert(edges[i].second);
    			graph[edges[i].second].insert(edges[i].first);
    		}
    		queue<int> q;
    		for (int i = 0; i < n; ++i) {
    			if (graph[i].size() == 1) q.push(i);
    		}
    		while (n > 2) {
    			int t = q.size();
    			n -= t;
    			while (t--) {
    				int leaf = q.front();
    				q.pop();
    				for (auto par : graph[leaf]) { // only one par
    					graph[par].erase(leaf);
    					if (graph[par].size() == 1)q.push(par);
    				}
    			}
    		}
    		vector<int> ans;
    		while (!q.empty()) {
    			ans.push_back(q.front());
    			q.pop();
    		}
    		return ans;
    	}
    };
    

    本代码提交AC,用时79MS。

    LeetCode Reconstruct Itinerary

    LeetCode Reconstruct Itinerary
    Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.
    Note:

    1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
    2. All airports are represented by three capital letters (IATA code).
    3. You may assume all tickets form at least one valid itinerary.

    Example 1:
    tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
    Return ["JFK", "MUC", "LHR", "SFO", "SJC"].
    Example 2:
    tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
    Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
    Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.


    给定一系列机票,每张机票标明了A→B的一段旅程,现在要求把所有的机票旅程连成一条完整的长距离航线,要求起点是JFK。如果有多条合法的航线,则输出字典序最小的那条。
    显然要转换为图的问题,每个机场转换为一个点,每张机票转换为一条边,然后从JFK开始DFS,保留每条合法的航线,然后sort取字典序最小的航线。
    把问题转换为图不难,使用hash给每个机场编号,然后新建一个图。在图中以JFK开始DFS也不难,每深入DFS一层,机票数目减1,当机票数目为0时,DFS结束,找到一条合法航线。
    我一开始是这么做的,但是TLE了,因为这样可能会进行很多次DFS, 找到多条航线,还需要sort取字典序最小的航线。
    有没有办法一次找到字典序最小的航线呢,只需要在DFS的时候,每次都从字典序最小的机场开始下一层DFS,这样第一次DFS成功的航线肯定是字典序最小的航线。
    所以我们给机场编号的时候,先使用map记录,map会自动按key的字典序从小到大排好。然后遍历map重新编号,并且用hash2记录编号和机场的对应关系。这样,在DFS的时候,从0→n的遍历,就自动是按字典序从小到大遍历。
    代码如下:

    class Solution {
    private:
    	bool dfs(string& ans, vector<string>& hash2, vector<vector<int>>& graph, int start, int lines) {
    		if (lines == 0) return true;
    		int n = hash2.size();
    		for (int i = 0; i < n; ++i) { // 字典序从小到大深搜
    			if (graph[start][i] > 0) {
    				--graph[start][i];
    				ans += hash2[i];
    				if (dfs(ans, hash2, graph, i, lines - 1))return true;
    				++graph[start][i];
    				ans = ans.substr(0, ans.size() - 3);
    			}
    		}
    		return false;
    	}
    public:
    	vector<string> findItinerary(vector<pair<string, string>> tickets) {
    		map<string, int> hash1;
    		vector<string> hash2;
    		int cnt = 0, n = tickets.size();
    		for (int i = 0; i < tickets.size(); ++i) { // 记录
    			hash1[tickets[i].first] = 0;
    			hash1[tickets[i].second] = 0;
    		}
    		for (auto it = hash1.begin(); it != hash1.end(); ++it) {
    			it->second = cnt++; // 字典序从小到大编号
    			hash2.push_back(it->first);
    		}
    		vector<vector<int>> graph(cnt, vector<int>(cnt, 0)); // 构图
    		for (int i = 0; i < tickets.size(); ++i)++graph[hash1[tickets[i].first]][hash1[tickets[i].second]];
    		int start = hash1["JFK"];
    		string ans = "JFK";
    		dfs(ans, hash2, graph, start, n); // 深搜
    		vector<string> Itinerary;
    		for (int i = 0; i <= ans.size() - 3; i += 3)Itinerary.push_back(ans.substr(i, 3));
    		return Itinerary;
    	}
    };
    

    本代码提交AC,用时22MS。

    LeetCode Evaluate Division

    LeetCode Evaluate Division
    Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.
    Example:
    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 ].
    The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.
    According to the example above:

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

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


    给定一系列的除法表达式,要计算另一些除法表达式的结果。比如知道a/b=2.0,b/c=3.0,问a/c=?。
    本题的解法是把一系列表达式转换为图,比如a/b=2.0转换为a指向b的边,边的值为2.0,同时b指向a的边的值为1/2.0。如果要求a/c,则在图中找一条a到c的边,并且把走过的边的值乘起来。
    构建图的过程先把表达式中的string编码成int,然后把已知的直连边加入到图中。对于要查询的边start/target,首先判断一下两个端点是否在图中,如果至少有一个端点不在图中,则无法求值,返回-1。否则,在图中DFS或BFS找到target,走过的路径乘积就是结果。
    题目说明所有values都是正数,所以不存在除0问题。
    DFS代码如下:

    class Solution {
    private:
    	bool dfs(vector<vector<double>>& graph, int start, int x, int y, int target) {
    		graph[start][y] = graph[start][x] * graph[x][y];
    		graph[y][start] = 1.0 / graph[start][y];
    		if(y == target)return true;
    		int n = graph.size();
    		for(int i = 0; i < n; ++i){
    			if(graph[start][i] == 0 && graph[y][i] != 0){
    				if(dfs(graph, start, y, i, target))return true;
    			}
    		}
    		return false;
    	}
    	double helper(vector<vector<double>>& graph, int start, int target) {
    		if (start == target)return 1.0;
    		else if (graph[start][target] != 0.0)return graph[start][target];
    		int n = graph.size();
    		for (int y = 0; y < n; ++y) {
    			if (y == start)continue;
    			if (graph[start][y] != 0.0) {
    				if (dfs(graph, start, start, y, target))return graph[start][target];
    			}
    		}
    		return -1.0;
    	}
    public:
    	vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
    		int cnt = 0, n = equations.size();
    		unordered_map<string, int> hash;
    		for (int i = 0; i < n; ++i) {
    			if (hash.find(equations[i].first) == hash.end())hash[equations[i].first] = cnt++;
    			if (hash.find(equations[i].second) == hash.end())hash[equations[i].second] = cnt++;
    		}
    		vector<vector<double>> graph(cnt, vector<double>(cnt, 0));
    		for (int i = 0; i < n; ++i) {
    			int x = hash[equations[i].first], y = hash[equations[i].second];
    			graph[x][x] = 1;
    			graph[y][y] = 1;
    			graph[x][y] = values[i];
    			graph[y][x] = 1.0 / values[i];
    		}
    		vector<double> ans;
    		for (int i = 0; i < queries.size(); ++i) {
    			if (hash.find(queries[i].first) == hash.end() || hash.find(queries[i].second) == hash.end())ans.push_back(-1.0);
    			else {
    				int x = hash[queries[i].first], y = hash[queries[i].second];
    				ans.push_back(helper(graph, x, y));
    			}
    		}
    		return ans;
    	}
    };
    

    本代码提交AC,用时3MS。
    BFS代码如下:

    class Solution {
    private:
    	double bfs(vector<vector<double>>& graph, int start, int target) {
    		if (start == target)return 1.0;
    		else if (graph[start][target] != 0.0)return graph[start][target];
    		int n = graph.size();
    		queue<int> q;
    		for(int x = 0; x < n; ++x){
    			if(x != start && graph[start][x] != 0)q.push(x);
    		}
    		while(!q.empty()){
    			int x = q.front();
    			if(x == target) return graph[start][target];
    			q.pop();
    			for(int y = 0; y < n; ++y){
    				if(graph[start][y] == 0 && graph[x][y] != 0){
    					graph[start][y] = graph[start][x] * graph[x][y];
    					graph[y][start] = 1.0 / graph[start][y];
    					q.push(y);
    				}
    			}
    		}
    		return -1.0;
    	}
    public:
    	vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
    		int cnt = 0, n = equations.size();
    		unordered_map<string, int> hash;
    		for (int i = 0; i < n; ++i) {
    			if (hash.find(equations[i].first) == hash.end())hash[equations[i].first] = cnt++;
    			if (hash.find(equations[i].second) == hash.end())hash[equations[i].second] = cnt++;
    		}
    		vector<vector<double>> graph(cnt, vector<double>(cnt, 0));
    		for (int i = 0; i < n; ++i) {
    			int x = hash[equations[i].first], y = hash[equations[i].second];
    			graph[x][x] = 1;
    			graph[y][y] = 1;
    			graph[x][y] = values[i];
    			graph[y][x] = 1.0 / values[i];
    		}
    		vector<double> ans;
    		for (int i = 0; i < queries.size(); ++i) {
    			if (hash.find(queries[i].first) == hash.end() || hash.find(queries[i].second) == hash.end())ans.push_back(-1.0);
    			else {
    				int x = hash[queries[i].first], y = hash[queries[i].second];
    				ans.push_back(bfs(graph, x, y));
    			}
    		}
    		return ans;
    	}
    };
    

    本代码提交AC,用时0MS,类似的题BFS显然要比DFS快,而且这题用BFS思路更清晰。