北京市建设集团有限公司绍兴seo管理

力扣785. 判断二分图

题目

题目解析及思路

题目要求将所有节点分成两部分，每条边的两个端点都必须在不同集合中

二分图：BFS/DFS/并查集

因为图不一定联通，所以枚举所有点都做bfs(如果没联通的话)

代码

class Solution {
public:bool isBipartite(vector<vector<int>>& graph) {int n = graph.size();vector<int> st(n,0);for(int i=0;i<n;i++){if(st[i] == 0){queue<int> q;q.push(i);//先染成1st[i] = 1;while(q.size()){int t = q.front();//equal为和t的颜色不一样的那个颜色int equal = (st[t] == 1 ? 2 : 1);q.pop();for(int v : graph[t]){//没被染色if(st[v] == 0){q.push(v);st[v] = equal;}//染过色而且是相同颜色else if(st[v] != equal){return false;}}}}}return true;}
};