力扣75——图深度优先搜索

总结leetcode75中的图深度优先搜索算法题解题思路。
上一篇：力扣75——二叉搜索树

1 钥匙和房间

题目：

有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。
你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，
即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入
所有 房间返回 true，否则返回 false。

题解：
我的方法：广度优先搜索。进入一个房间t，拿到里面的钥匙tmp，然后把钥匙tmp压入队列q中。while循环从队列q拿钥匙，直到q空了为止。最后检查所有房间visit是否都被访问。
官方代码：深度优先搜索。利用递归函数dfs：进入一个房间，拿到钥匙，再用for循环调用dfs函数。

class Solution {
public:bool canVisitAllRooms(vector<vector<int>>& rooms) {int numRooms = rooms.size();vector<int> visit(numRooms,0);visit[0] = 1;vector<int> tmp;queue<int> q;q.push(0);while (!q.empty()) {tmp = rooms[q.front()];q.pop();if (!tmp.empty()) {for (int t : tmp) {if (visit[t] == 1)continue;q.push(t);visit[t] = 1;}}}for (int v : visit) {if (v == 0) return false;}return true;}
};
//官方的代码更简洁合理
/*
class Solution {
public:vector<int> vis;int num;void dfs(vector<vector<int>>& rooms, int x) {vis[x] = true;num++;for (auto& it : rooms[x]) {if (!vis[it]) {dfs(rooms, it);}}}bool canVisitAllRooms(vector<vector<int>>& rooms) {int n = rooms.size();num = 0;vis.resize(n);dfs(rooms, 0);return num == n;}
};
*/

2 省份数量

题目：

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，
且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和
第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。返回矩阵中 省份 的数量。

题解：
深度优先搜索。for遍历每个城市，用递归函数dfs找到所有与当前城市i直接或间接相连的城市，用visit来标记已经搜索过的城市。

class Solution {
public:int findCircleNum(vector<vector<int>>& isConnected) {int nums = 0, nC = isConnected.size();vector<int> visit(nC, 0);for (int i = 0; i < nC; i++) {if (visit[i] == 0) {nums++;dfs(isConnected, visit, i);}}return nums;}void dfs(vector<vector<int>>& isConnected,vector<int> & visit,int i) {visit[i] = 1;for (int j = 0; j < isConnected.size(); j++) {if (isConnected[i][j] == 1&& visit[j] == 0) {dfs(isConnected, visit, j);}}}
};

3 重新规划路线

题目：

n 座城市，从 0 到 n-1 编号，其间共有 n-1 条路线。因此，要想在两座不同城市之间旅行只有
唯一一条路线可供选择（路线网形成一颗树）。去年，交通运输部决定重新规划路线，以改变交通
拥堵的状况。路线用 connections 表示，其中 connections[i] = [a, b] 表示从城市 a 到 b 的一条有向
路线。今年，城市 0 将会举办一场大型比赛，很多游客都想前往城市 0 。
请你帮助重新规划路线方向，使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。
题目数据 保证 每个城市在重新规划路线方向后都能到达城市 0 。

题解：
广度优先搜索。目的是将所有路线的方向都朝着城市0，所以遍历所有与城市0直接相连的城市，然后对这每一个相连的城市进行广度优先搜索，更改那些方向错误的路线。具体的过程在代码中有注释。

class Solution {
public:int minReorder(int n, vector<vector<int>>& connections) {vector<vector<int>> conn_idx(n, vector<int>());//这里使用了类似于邻接表的方法，将和节点有关的连接的id序号加入到对应的向量中//这样在后面遍历的时候，只要查找connections里面对应的id即可//要注意这里连接两端都加入了连接的序号for (int i = 0; i < connections.size(); i++) {conn_idx[connections[i][0]].push_back(i);conn_idx[connections[i][1]].push_back(i);}vector<bool> vi(connections.size(), false);//此处标志的是某条边是否被访问过，而不是某个点是否被访问过int ans = 0;queue<int> que;que.push(0);while (!que.empty()) {auto q = que.front();que.pop();//这个循环是对和节点q相关的连接进行遍历，通过上面存储的连接的id进行遍历for (auto idx : conn_idx[q]) {if (vi[idx]) continue;vi[idx] = true;int a = connections[idx][0];//连接的起始int b = connections[idx][1];//连接的终点ans += (a == q);//如果当前点是出的，那么要修改为入，ans++a = (a == q) ? b : a;que.push(a);}}return ans;}
};

4 除法求值

题目：

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] 
= [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示
单个变量的字符串。
另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根
据已知条件找出 Cj / Dj = ? 的结果作为答案。返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现
了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
注意：未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。

题解：
并查集。
1 先定义1个unordered_map类型的parent，它记录了一个数的被除数，被除数的被除数是它自己。
2 再定义1个unordered_map类型的mp，记录1个数除被除数得到的值。
3 接着定义函数find()，该函数可以找到一个数的祖先。在这个过程中，如果发现一个数的祖先跟它隔了2代或更多代，就递归进行压缩，并修改对应的mp值。
4 然后，通过for循环遍历equations，将所以除法公式及其结果记录好。
5 最后，计算queries中的问题。如果被除数或除数不存在于parent中，则无法求解；如果除数和被除数的祖先不是同一个，也无法求解；如果除数和被除数是同一个祖先，则直接用它们的mp值做除法即可。

class Solution {
public:unordered_map<string, string> parent;unordered_map<string, double> mp;string find(string x){if(parent[x] == x)  return x;string px = parent[x];string res =  parent[x] = find(parent[x]);    mp[x] *= mp[px];return res;}vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {int n = equations.size();for(int i = 0; i < n; i ++ ){string a = equations[i][0], b = equations[i][1];double v = values[i];if(parent.find(a) == parent.end() && parent.find(b) == parent.end()){parent[a] = a; parent[b] = a;mp[b] = v, mp[a] = 1.0;}else if(parent.find(a) == parent.end()){parent[a] = a; string pb = find(b);mp[a] = 1.0;mp[pb] = v / mp[b];parent[pb] = a;}else if(parent.find(b) == parent.end()){parent[b] = a;mp[b] = v;}else{string pa = find(a), pb = find(b);if(pa == pb)    continue;parent[pb] = pa;mp[pb] = mp[a] * v / mp[b];} }vector<double> res;for(auto &item : queries){string a = item[0], b = item[1];if(parent.find(a) == parent.end() || parent.find(b) == parent.end())    res.push_back(-1.0);else{string pa = find(a), pb = find(b);if(pa != pb)    res.push_back(-1.0);else    res.push_back(mp[b] / mp[a]);}}return res;}
};

1-4 解题总结

a 题目类型总结：

• 题目1：从1个节点出发，是否可以到达所有节点。
• 题目2：所有节点构成几个连通域。
• 题目3：从任意节点出发，是否可以到达某个节点。
• 题目4：节点1是否可以到达节点2。

b 题目1和题目3本质上是一样的，只是边的方向相反了而已。他们既可以使用深度优先搜索，也可以使用广度优先搜索。
c 题目2既可以使用深度优先搜索，也可以使用广度优先搜索。
d 题目4是检查两个点之间是否连通，所以，用深度优先搜索更合适。
e 这些题目不限制是否会重复经过某个节点，只考虑哪些节点是相通的。