力扣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;}
};