785、判断二分图
题目：
https://leetcode-cn.com/problems/is-graph-bipartite/
题解：
此题重点在于分析题目，到底如何才算一个二分图。根据题目分析，一个图的所有节点分成两个集合A和B，且途中每一条边的两个节点必须一个来自A一个来自B。说白了，就是图中任意两条边必须要属于不同的集合。在code中节点属于不同的集合使用颜色来表示。那么就可以遍历图中所有的节点，并将其着色A，然后再将该节点所有相邻的节点进行着色B，在遍历的过程中一旦发现相邻节点已着色并且着色是A（相邻颜色相同），那么就说明不满足二分图的条件。直接结束遍历，返回false。
题目提供了邻接表，邻接表每一行的元素恰好代表着”行号点”所有相邻的点。因此，利用邻接表即可进行遍历，本题使用的是深度遍历方法。
注意：由于题目没有说图是连通图，所以非连通图一次是遍历不完的，因此需要对每一个节点都执行一次遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
private:
static int const RED = 0;
static int const GREEN = 1;
static constexpr int UNCOLORED = 2;
bool result;
vector<int> color;
public:
void bfs(int n, int flag, vector<vector<int>>& graph) {
color[n] = flag;
int unflag = (flag == RED ? GREEN : RED);
for(int go : graph[n]) {
if(color[go] == UNCOLORED) {
bfs(go, unflag, graph);
if(!result) {
return;
}
} else if (color[go] != unflag) {
result = false;
return;
}
}
}
bool isBipartite(vector<vector<int>>& graph) {
color.assign(graph.size(), UNCOLORED);
result = true;
for(int i = 0; (i < graph.size()) && result; i++) {
if(color[i] == UNCOLORED) {
bfs(i, RED, graph);
}
}
return result;
}
};
|
上一篇：15-三数之和/18-四数之和
下一篇：IDS/IPS
