LeetCode算法练习——深度优先搜索 DFS(3)
更多干货就在我的个人博客 BlackBlog.tech 欢迎关注！
也可以关注我的csdn博客：黑哥的博客
谢谢大家！
LeetCode Everyday!
我们继续LeetCode之旅，这一篇再完成十个题，我们就进入下一个章节。做了一段时间LeetCode。感觉真的挺不错的，以前数据结构课上的很多内容又回以前来了。LeetCode很适合锻炼基础功，题目也很清晰。很不错。建议各位如果有时间，可以从中级算法开始练习。一日一题，都会有很大提升。
给个目录：
LeetCode638 大礼包
LeetCode542 01矩阵
LeetCode529 扫雷游戏
LeetCode547 朋友圈
LeetCode576 出界的路径数
LeetCode721 账户合并
LeetCode743 网络延迟时
LeetCode785 判断二分图
LeetCode841 钥匙和房间
LeetCode207 课程表
LeetCode638 大礼包
题目
在LeetCode商店中， 有许多在售的物品。
然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。
现给定每个物品的价格，每个大礼包包含物品的清单，以及待购物品清单。请输出确切完成待购清单的最低花费。
每个大礼包的由一个数组中的一组数据描述，最后一个数字代表大礼包的价格，其他数字分别表示内含的其他种类物品的数量。
任意大礼包可无限次购买。
示例 1:
输入: [2,5], [[3,0,5],[1,2,10]], [3,2]
输出: 14
解释:
有A和B两种物品，价格分别为¥2和¥5。
大礼包1，你可以以¥5的价格购买3A和0B。
大礼包2， 你可以以¥10的价格购买1A和2B。
你需要购买3个A和2个B， 所以你付了¥10购买了1A和2B（大礼包2），以及¥4购买2A。
示例 2:
输入: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
输出: 11
解释:
A，B，C的价格分别为¥2，¥3，¥4.
你可以用¥4购买1A和2B，也可以用¥9购买2A，2B和1C。
你需要买1A，2B和1C，所以你付了¥4买了1A和1B（大礼包1），以及¥3购买1B， ¥4购买1C。
你不可以购买超出待购清单的物品，尽管购买大礼包2更加便宜。
说明:
最多6种物品， 100种大礼包。
每种物品，你最多只需要购买6个。
你不可以购买超出待购清单的物品，即使更便宜。
C++代码
class Solution {
public:
//判断是否能够放入当前这个礼包
bool valid(vector<int> special_single, vector<int> needs){
for(int i=0;i<needs.size();i++){
if(special_single[i]>needs[i]) return false;
}
return true;
}
int shoppingOffers(vector<int> &price, vector<vector<int>> &special, vector<int> &needs) {
int min_money = 0; //表示最小值
//如果全部买单独的物品
for(int i=0;i<needs.size();i++){
min_money += price[i] * needs[i];
}
//遍历所有礼包
for(int i=0;i<special.size();i++){
if(valid(special[i],needs)){
//如果礼包可以购买的话
vector<int> new_needs; //新建一个数组 表示新的needs
for(int j=0;j<needs.size();j++)
new_needs.push_back(needs[j]-special[i][j]); //新的needs = 旧的needs - 礼包中物品的个数
int money_tmp = shoppingOffers(price,special,new_needs) + special[i].back(); //将当前礼包的几个加到money_temp上，同时继续遍历
min_money = min(min_money,money_tmp); //最后求出最低价格
}
}
return min_money;//返回最低价格
}
};
体会
这个题不难，但鉴于我抠脚的水平，竟然做了很久。我们采取这样的思路，首先单独买下所有的产品，计算出价格，之后我们遍历礼包进行搜索，在搜索的过程中每次都要更新needs，这样可以实现零售+礼包的方式，每次记录下礼包的价格，搜索结束后，找到最小的价格，返回。
LeetCode542 01矩阵
题目
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1:
输入:
0 0 0
0 1 0
0 0 0
输出:
0 0 0
0 1 0
0 0 0
示例 2:
输入:
0 0 0
0 1 0
1 1 1
输出:
0 0 0
0 1 0
1 2 1
注意:
给定矩阵的元素个数不超过 10000。
给定矩阵中至少有一个元素是 0。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。
C++代码
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
queue<pair<int,int>> que;
//将矩阵中所有的0 坐标入列， 将所有的1设置为INT_MAX
for(int i=0;i<matrix.size();i++){
for(int j=0;j<matrix[0].size();j++)
if(matrix[i][j]==0) que.push(make_pair(i,j));
else if(matrix[i][j]==1) matrix[i][j] = INT_MAX;
}
//循环直到队列为空
while(!que.empty()){
auto q = que.front(); //将队列的首元素取出来
que.pop(); //队首出列
vector<pair<int,int>> dirs ={{0,1},{0,-1},{1,0},{-1,0}}; //四个方向的坐标
//对四个方向进行尝试
for(auto dir : dirs){
//计算新的坐标
int x = q.first + dir.first;
int y = q.second + dir.second;
//如果x，y超过边界 或者 x y的数值比当前小 则不用更新
if(x<0 || x>matrix.size()-1 || y<0 || y>matrix[0].size()-1 || matrix[x][y]<= matrix[q.first][q.second]) continue;
//更新当前位置的 数据 。可以理解为深度
matrix[x][y] = matrix[q.first][q.second] + 1;
//将更新后的点存入队列
que.push({x,y});
}
}
return matrix;
}
};
体会
这个题，开始我尝试用dfs去解答，如果使用dfs，需要遍历每一个为1的点，非常耗时间，最终超时了。这个中周围距离的题目，使用bfs是更好的方式。
bfs的思路是逐层更新，首先我们将所有的1都改为无穷大。从一个0开始，逐层向外更新，每次只考虑周围的四个节点，如果目标节点的值大于源节点的值，就证明我们给目标节点找到了一条更短的路，我们更新目标节点，否则目标节点保持不变。bfs需要使用队列进行存储，先将所有的0入列，作为起点，之后每次更新过的节点都要入列，用来实现祝层向外的效果。
给一个DFS超时的代码 T.T
void dfs(vector<vector<int>> &matrix,vector<vector<bool>> visited,int depth,int x,int y,int src_x,int src_y){
if(x>matrix.size()-1 || x<0 || y>matrix[0].size()-1 ||y<0 || visited[x][y]) return;
if(matrix[x][y]==0) {
if(depth<matrix[src_x][src_y]) matrix[src_x][src_y] = depth;
visited[x][y]= false;
return;
}
visited[x][y]= true;
dfs(matrix,visited,depth+1,x,y+1,src_x,src_y);
dfs(matrix,visited,depth+1,x,y-1,src_x,src_y);
dfs(matrix,visited,depth+1,x+1,y,src_x,src_y);
dfs(matrix,visited,depth+1,x-1,y,src_x,src_y);
}
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
vector<vector<bool>> visited(matrix.size(),vector<bool>(matrix[0].size(),false));
for(int i=0;i<matrix.size();i++)
for(int j=0;j<matrix[0].size();j++)
if(matrix[i][j]==1) matrix[i][j]=INT_MAX;
for(int i=0;i<matrix.size();i++)
for(int j=0;j<matrix[0].size();j++) {
dfs(matrix, visited, 0, i, j, i, j);
}
return matrix;
}
LeetCode529 扫雷游戏
题目
让我们一起来玩扫雷游戏！
给定一个代表游戏板的二维字符矩阵。 'M' 代表一个未挖出的地雷，'E' 代表一个未挖出的空方块，'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（'1' 到 '8'）表示有多少地雷与这块已挖出的方块相邻，'X' 则表示一个已挖出的地雷。
现在给出在所有未挖出的方块中（'M'或者'E'）的下一个点击位置（行和列索引），根据以下规则，返回相应位置被点击后对应的面板：
如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为 'X'。
如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的方块都应该被递归地揭露。
如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。
如果在此次点击中，若无更多方块可被揭露，则返回面板。
示例 1:
输入:
[['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'M', 'E', 'E'],
['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'E', 'E', 'E']]
Click : [3,0]
输出:
[['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
示例 2:
输入:
[['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
Click : [1,2]
输出:
[['B', '1', 'E', '1', 'B'],
['B', '1', 'X', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
注意:
输入矩阵的宽和高的范围为 [1,50]。
点击的位置只能是未被挖出的方块 ('M' 或者 'E')，这也意味着面板至少包含一个可点击的方块。
输入面板不会是游戏结束的状态（即有地雷已被挖出）。
简单起见，未提及的规则在这个问题中可被忽略。例如，当游戏结束时你不需要挖出所有地雷，考虑所有你可能赢得游戏或标记方块的情况。
C++代码
class Solution {
public:
void dfs(vector<vector<char>>& board,vector<int> click){
int x = click[0];
int y = click[1];
int width = board[0].size();
int height = board.size();
//周围八个格子的坐标
vector<pair<int,int>> dirs ={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
if(x<0 || x>height-1 || y<0 || y>width-1) return;
int mine_count = 0;
遍历周围八个格子同时记录雷的个数
for( auto dir : dirs){
int x_new = x+dir.first;
int y_new = y+dir.second;
if(x_new<0 || x_new>height-1 || y_new<0 || y_new>width-1) continue;
if(board[x_new][y_new] == 'M' || board[x_new][y_new] == 'X' ) mine_count++;
}
//如果雷的个数不为0 这个位置填上雷的个数
if(mine_count!=0) board[x][y] = mine_count +'0';
else { //否则这个位置填上 B 并继续dfs
board[x][y] = 'B';
for(auto dir :dirs){
int new_x = x + dir.first;
int new_y = y +dir.second;
if(new_x>=0 && new_x<height && new_y>=0 && new_y<width && board[new_x][new_y]=='E') //如果即将遍历的点是 E 才遍历，如果是B证明遍历过了，防止死循环
dfs(board,{x+dir.first,y+dir.second});
}
}
}
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
if(board[click[0]][click[1]]=='M') board[click[0]][click[1]]='X';
else dfs(board,click);
return board;
}
};
体会
比较经典的体会，dfs算法完成扫雷。从给定的点开始dfs遍历，每到打一个新点，检查周围八个位置的雷的个数，如果雷的个数不为0，这个点设置为数字，否则这个点就是B。如果这个点是B则继续dfs周围的八个点，搜索的时候要注意 下一个点是E才搜索，不然会陷入死循环。
LeetCode547 朋友圈
题目
班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
示例 1:
输入:
[[1,1,0],
[1,1,0],
[0,0,1]]
输出: 2
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。
示例 2:
输入:
[[1,1,0],
[1,1,1],
[0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。
注意：
N 在[1,200]的范围内。
对于所有学生，有M[i][i] = 1。
如果有M[i][j] = 1，则有M[j][i] = 1。
C++代码
class Solution {
public:
int dfs(vector<vector<int>> M, vector<bool> &visited, int p) {
if(visited[p]) return 0; //如果当前节点被访问过 直接结束
else {
visited[p] = true; //将当前节点标记为访问过
int count =1;
for (int i = 0; i < M.size(); i++) {//遍历 找到当前这个人的朋友
if (M[p][i] == 1 && !visited[i] && i != p) { //如果M数组值为1 且这个人不是自己 就是朋友
count += dfs(M, visited, i); //接着找朋友
}
}
return count; //最后返回一共找了几次朋友 虽然并不需要这个值 只要有朋友就可以了
}
}
int findCircleNum(vector<vector<int>>& M) {
int py = 0; //朋友圈的个数
vector<bool> visited(M.size(), false);//初始化一个visited数组 用于记录访问的情况
for(int i=0;i<M.size();i++)
if(dfs(M,visited,i)) py++;//如果dfs的结果不是0，证明存在朋友圈。
return py;
}
};
体会
题目挺经典的，一道dfs无回溯题目。将这个题目仔细解读一下，就可以发现我们需要求朋友关系图中的连通分量。采用dfs算法，对每一个人都进行搜索，如果找到了朋友，就把朋友作为起点继续搜索。使用visited数组记录每个人被访问的状态。dfs返回值为int，只要存在朋友圈，返回值就不为0，否则返回0，证明没有找到朋友圈。
LeetCode576 出界的路径数
题目
给定一个 m × n 的网格和一个球。球的起始坐标为 (i,j) ，你可以将球移到相邻的单元格内，或者往上、下、左、右四个方向上移动使球穿过网格边界。但是，你最多可以移动 N 次。找出可以将球移出边界的路径数量。答案可能非常大，返回 结果 mod 109 + 7 的值。
示例 1：
输入: m = 2, n = 2, N = 2, i = 0, j = 0
输出: 6
示例 2：
输入: m = 1, n = 3, N = 3, i = 0, j = 1
输出: 12
说明:
球一旦出界，就不能再被移动回网格内。
网格的长度和高度在 [1,50] 的范围内。
N 在 [0,50] 的范围内。
C++代码
class Solution {
public:
int findPaths(int m, int n, int N, int i, int j) {
vector<vector<vector<int>>> dp(N+1,vector<vector<int>>(m,vector<int>(n,0))); //新建一个dp数组
//dp[k][i][j]表示剩余k步时，起点在[i,j]时的出度数
for(int k=1;k<=N;k++){
for(int x=0;x<m;x++){
for(int y=0;y<n;y++){
long long v1,v2,v3,v4;
if(x==0) v1=1;else v1 = dp[k-1][x-1][y]; //没有到达最顶 就向上移动一位
if(x==m-1) v2=1;else v2 = dp[k-1][x+1][y]; //没有到达最底 就向下移动一位
if(y==0) v3=1;else v3 = dp[k-1][x][y-1]; //没有到达最左 就向左移动一位
if(y==n-1) v4=1;else v4 = dp[k-1][x][y+1]; //没有到达最右 就向右移动一位
dp[k][x][y] = (v1+v2+v3+v4)%1000000007;//dp[k][i][j] 讲就是将四个方向的出度进行求和
}
}
}
return dp[N][i][j];
}
};
体会
这个题其实不是搜索题，是一道DP题。我也写了一份暴搜的代码，运行没问题，但是肯定会超时。底下有这份代码。
DP的思路就是将大问题划分为小问题，列出状态转移方程。这道题 问题[k][i][j]：表示剩余k步时，起点在[i,j]的出届数，这个问题可以转化为 剩余k-1步，起点[i,j]四个方向各点出届数的和。所以状态转移方程 dp[k][i][j] = dp[k-1][i-1][j] + dp[k-1][i+1][j] + dp[k-1][i][j-1] + dp[k-1][i][j+1]，编程实现即可。
附：暴搜代码：
int res = 0;
int findPaths(int m, int n, int N, int i, int j) {
dfs(m,n,N,i,j,0);
return res;
}
void dfs(int m,int n,int N,int i, int j,int now){
if(i<0 || i>m-1 || j<0 || j>n-1){
res ++;
return;
}
if(now == N) return;
dfs(m,n,N,i+1,j,now+1);
dfs(m,n,N,i-1,j,now+1);
dfs(m,n,N,i,j+1,now+1);
dfs(m,n,N,i,j-1,now+1);
}
LeetCode721 账户合并
题目
给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该帐户的邮箱地址。
现在，我们想合并这些帐户。如果两个帐户都有一些共同的邮件地址，则两个帐户必定属于同一个人。请注意，即使两个帐户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的帐户，但其所有帐户都具有相同的名称。
合并帐户后，按以下格式返回帐户：每个帐户的第一个元素是名称，其余元素是按顺序排列的邮箱地址。accounts 本身可以以任意顺序返回。
例子 1:
Input:
accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
Output: [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'], ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
Explanation:
第一个和第三个 John 是同一个人，因为他们有共同的电子邮件 "johnsmith@mail.com"。
第二个 John 和 Mary 是不同的人，因为他们的电子邮件地址没有被其他帐户使用。
我们可以以任何顺序返回这些列表，例如答案[['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']，
['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']]仍然会被接受。
注意：
accounts的长度将在[1，1000]的范围内。
accounts[i]的长度将在[1，10]的范围内。
accounts[i][j]的长度将在[1，30]的范围内。
C++代码
class Solution {
public:
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
map<string,string> root;
map<string,string> owner;
map<string,set<string>> m;
vector<vector<string>> res;
//初始化root 与 owner，开始时 每一个元素都是自己的根节点
for(int i=0;i<accounts.size();i++){
for(int j=0;j<accounts[i].size();j++){
root[accounts[i][j]] = accounts[i][j];
owner[accounts[i][j]] =accounts[i][0];
}
}
//连接同源节点
for(int i=0;i<accounts.size();i++){
string tmp = find(accounts[i][1],root);
for(int j=2;j<accounts[i].size();j++){
root[find(accounts[i][j],root)] = tmp;
}
}
//根据root制作m，m中的每一个元是一个独立树
for(int i=0;i<accounts.size();i++){
for(int j=1;j<accounts[i].size();j++)
m[find(accounts[i][j],root)].insert(accounts[i][j]);
}
//通过m得到最后res
for(auto key : m){
vector<string> one(key.second.begin(), key.second.end());
one.insert(one.begin(),owner[key.first]);
res.push_back(one);
}
return res;
}
//递归查询根节点
string find(string str,map<string,string>&root){
if(str == root[str])
return str;
else return find(root[str],root);
}
};
体会
这个题还是值得一讲的。这是一道运用并查集的题型。最小生成树、亲戚关系的判定、确定无向图的连通子图个数、最小公共祖先问题等，都要用到并查集。我们将题目给的样例简化成如下，进行讲解。
J:A B
J:C
J:B D
M:E
首先，初始化root owner。初始化的root中 每一个节点都是自己的根节点.
root: owner: m:
A:A A:J
B:B B:J
C:C C:J
D:D D:J
E:E E:M
根据account连接同源节点得到
root: owner: m:
A:A A:J
B:A B:J
C:C C:J
D:A D:J
E:E E:M
可以看到，现在的root中，非源节点的节点已经连接到了其源节点。这个效果来自于find的递归查询。
通过root建立m
root: owner: m:
A:A A:J A:ABD
B:A B:J C:C
C:C C:J E:E
D:A D:J
E:E E:M
源节点相同的节点已经形成了一棵树。
通过m与owner便可构建出最后的答案。
LeetCode743 网络延迟时
题目
有 N 个网络节点，标记为 1 到 N。
给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。
现在，我们向当前的节点 K 发送了一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。
注意:
N 的范围在 [1, 100] 之间。
K 的范围在 [1, N] 之间。
times 的长度在 [1, 6000] 之间。
所有的边 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 1 <= w <= 100。
C++代码
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int N, int K) {
queue<int> q;
vector<int> each_time(N+1,INT_MAX); //each_time表示从K到每个节点的最短距离，初始化为INT_MAX
each_time[K] = 0; //到自己的距离为0
each_time[0] = 0; //0不存在 置为0
//队列模拟bfs算法
q.push(K);
while(!q.empty()){
int curr = q.front();
for(auto i:times){
//如果 目标节点的值 大于 当前节点+当前节点到目标节点的路径 就更新目标节点，并把目标节点放入队列
if(curr == i[0] && each_time[i[1]]>each_time[i[0]]+i[2])
{
q.push(i[1]);
each_time[i[1]] = each_time[i[0]] + i[2];
}
}
q.pop();
}
int ans=0;
//从所有的最短路径中 找出最大的
for(auto a: each_time){
ans = max(a,ans);
}
return (ans == INT_MAX) ? -1 : ans; //输出-1还是输出最大值
}
};
体会
本题题目可以化简为求单源最短路径中的最大值。我们可以使用Dijkstra算法求出单源最短路径，再求最大值，但是这样速度比较慢。这个题我采用BFS算法，速度要快一些。思路很简单，初始节点入队列，在 times 中查找初始节点的目标节点，并对目标节点进行更新。//如果目标节点的值大于当前节点+路径长度就更新目标节点，并把目标节点放入队列。这个思路跟Dijkstra是一样的。最后输出所有最短路径中的最大值就可以，输出时注意判断是否有解。
LeetCode785 判断二分图
题目
给定一个无向图graph，当这个图为二分图时返回true。
如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。
graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。
示例 1:
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释:
无向图如下:
0----1
| |
| |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。
示例 2:
输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
输出: false
解释:
无向图如下:
0----1
| \ |
| \ |
3----2
我们不能将节点分割成两个独立的子集。
注意:
graph 的长度范围为 [1, 100]。
graph[i] 中的元素的范围为 [0, graph.length - 1]。
graph[i] 不会包含 i 或者有重复的值。
图是无向的: 如果j 在 graph[i]里边, 那么 i 也会在 graph[j]里边。
C++代码
class Solution {
public:
bool dfs(vector<vector<int>>& graph,vector<int> &color,int pos,int c){
color [pos] =c;//将当前点的颜色标记为 c
for(int i=0;i<graph[pos].size();i++){ //寻找当前点的邻居
if(color[graph[pos][i]] == c) return false; //如果当前点的邻居的颜色也是c 则证明重复 返回
if(color[graph[pos][i]] == 0 && !dfs(graph,color,graph[pos][i],-c)) return false; //如果该邻居的还没上色 则给他上-c色，dfs下去，如果全部上色成功，则返回true
}
return true;
}
bool isBipartite(vector<vector<int>>& graph) {
vector<int> color(graph.size(),0);
//遍历所有节点 防止出现图不连通的情况
for(int i=0;i<graph.size();i++){
if(color[i] == 0){
//如果当前点没有上色，则从该点开始上色 初始颜色为1
if(!dfs(graph,color,i,1)){
return false;
}
}
}
return true;
}
};
体会
判断二分图，我们利用染色的方式来解决。使用dfs，对每一个节点先染上C色，判断他的邻居节点，如果颜色也是C，证明冲突，返回false；如果邻居节点没有染色，则尝试给邻居染上-c色，逐层dfs，如果全部染色成功，返回true。
注意，这个题需要对所有的节点都尝试dfs，因为不是每一组输入的图都是连通的。
LeetCode841 钥匙和房间
题目
有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。
在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。
最初，除 0 号房间外的其余所有房间都被锁住。
你可以自由地在房间之间来回走动。
如果能进入每个房间返回 true，否则返回 false。
示例 1：
输入: [[1],[2],[3],[]]
输出: true
解释:
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。
示例 2：
输入：[[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。
提示：
1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
所有房间中的钥匙数量总计不超过 3000。
C++代码
class Solution {
public:
void dfs(vector<vector<int>> &rooms,vector<int> &visited,int room){
if(visited[room]) return; //如果当前节点被访问 就返回
visited[room] = 1; //将当前节点设置为访问
for(int i=0;i<rooms[room].size();i++){ //遍历当前节点的邻居
dfs(rooms,visited,rooms[room][i]);
}
}
bool canVisitAllRooms(vector<vector<int>>& rooms) {
vector<int> visited(rooms.size(),0); //建立一个visited数组
dfs(rooms,visited,0); //从0点开始查询
if(find(visited.begin(),visited.end(),0)==visited.end()) return true; //如果所有的节点都被访问了 就返回true 反之false
else return false;
}
};
体会
经典dfs无回溯题目，直接按思路写就可以，没有难度。具体内容请看注释。当我看到通过率时46.6%时，我就感觉可以1A了。哈哈哈哈哈
LeetCode207 课程表
题目
现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？
示例 1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
说明:
输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
提示:
这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
拓扑排序也可以通过 BFS 完成。
C++代码
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
map<int,vector<int>> linkGraph;
vector<int> in(numCourses,0);
vector<int> out(numCourses,0);
vector<int> visited(numCourses,0);
//构造图的邻接表
for(auto p:prerequisites){
linkGraph[p.first].push_back(p.second);
in[p.second]++;
out[p.first]++;
}
queue<int> que;
//将所有入度为0的点 放入队列中
for(int i=0;i<in.size();i++)
if(in[i]==0) que.push(i);
while(!que.empty()){
int tmp = que.front(); // 去除队列首元素
que.pop();
for(auto i : linkGraph[tmp]){ //删除该节点 要将与其连接的节点的入度都-1
in[i]--;
if(in[i]==0){ //如果入度为0 添加进队列
que.push(i);
}
}
}
if(*max_element(in.begin(),in.end())==0) return true; //入度全为0 证明 环
else return false;
}
};
体会
这一份应该是网上本题最清晰简单的解法了。考察拓扑排序，第一次坐到这个问题。去一个图是否是拓扑可排的方法就两种，DFS每次删去出度为0的节点，BFS每次删去入度为0的节点，最终判断是否所有的出度/入度都为0，如果都为0，证明无环，拓扑可排。
思路：将边缘列表转换为临接表，同是记录下每一个节点的入度。
将所有入度为0的节点，入队。
每次取出队首元素，删除它，将其连接节点的入度-1，如果入度为0的话，放入队列中，重复此过程。
最后判断所有的入度是否都是0，都是则无环，输出。
