785. Is Graph Bipartite?
2024-10-21 15:58:44
Given an undirected graph
, return true
if and only if it is bipartite.
Recall that a graph is bipartite if we can split it's set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.
The graph is given in the following form: graph[i]
is a list of indexes j
for which the edge between nodes i
and j
exists. Each node is an integer between 0
and graph.length - 1
. There are no self edges or parallel edges: graph[i]
does not contain i
, and it doesn't contain any element twice.
Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation:
The graph looks like this:
0----1
| |
| |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.
Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation:
The graph looks like this:
0----1
| \ |
| \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.
Note:
graph
will have length in range[1, 100]
.graph[i]
will contain integers in range[0, graph.length - 1]
.graph[i]
will not containi
or duplicate values.- The graph is undirected: if any element
j
is ingraph[i]
, theni
will be ingraph[j]
.
class Solution {
public:
bool dfs(vector<vector<int> >& graph, vector<int>& state, int i, int color){
for (int j = ; j<graph[i].size(); j++){
if (state[graph[i][j]] == ){ //没有遍历到时
state[graph[i][j]] = -color; //标记该节点颜色同时继续搜索
return dfs(graph, state, graph[i][j], -color);
}
else if (state[graph[i][j]] == color){ //邻居节点中与该节点颜色相同则返回false
return false;
}
}
return true;
}
bool isBipartite(vector<vector<int>>& graph) {
int node_num = graph.size();
vector<int> state(node_num,);
int result = true;
for(int i=; i<graph.size(); i++){
if(state[i]== && !dfs(graph, state, i, ))
result = false;
}
return result;
}
};
最新文章
- Linux流量监控工具 - iftop
- csuoj 1391: Boiling Vegetables
- MTP in Android详解
- SpringDataJPA的几个使用记录
- [最近公共祖先] POJ 3728 The merchant
- 我也想聊聊 OAuth 2.0 —— Access Token
- Win2003_IIS+PHP+MYSQL 全能服务器配置
- Codeforces Round #Pi (Div. 2) B. Berland National Library set
- Illustrator软件中eps和ai格式的区别
- echarts的使用
- 酷派D530刷机指引之官方ROM
- 原生AJAX如何异步提交数据?
- 《windows程序设计》学习_1:初识windows程序
- html基础及心得
- 利用 gperftools 对nginx mysql 内存管理 性能优化
- sql 两种分页offset和row_number简单分析
- 使用NetronGraphLib类库开发Qfd质量屋编制工具
- Timus Online Judge:ural:1006. Square Frames
- 基于usb4java的usb通讯
- Linux中用find命令查找当前文件夹下的.elf文件
热门文章
- How RTT works
- Gradle Goodness: Add Incremental Build Support to Tasks
- ios - 沙盒和NSBundle
- 【学时总结】 ◆学时&#183;III◆ 二分图
- Linux各个文件及其含义
- Linux下onvif客户端获取ipc摄像头 GetProfiles:获取h265媒体信息文件
- 使用xampp发现php的date()函数与本地相差7个小时
- pycharm使用杂记
- Angularjs中的超时处理
- Mysql only_full_group_by 引起的错误