力扣785.判断二分图

力扣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); //先染成1 st[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; } };