---
# System prepended metadata

title: 785. Is Graph Bipartite?
tags: [bfs, Leetcode, medium, python, c++, graph]

---

###### tags: `Leetcode` `medium` `graph` `bfs` `python` `c++`

# 785. Is Graph Bipartite?

## [題目連結:] https://leetcode.com/problems/is-graph-bipartite/

## 題目:
There is an **undirected** graph with ```n``` nodes, where each node is numbered between ```0``` and ```n - 1```. You are given a 2D array ```graph```, where ```graph[u]``` is an array of nodes that node ```u``` is adjacent to. More formally, for each ```v``` in ```graph[u]```, there is an undirected edge between node ```u``` and node ```v```. The graph has the following properties:

* There are no self-edges (```graph[u]``` does not contain ```u```).
* There are no parallel edges (```graph[u]``` does not contain duplicate values).
* If v is in ```graph[u]```, then ```u``` is in ```graph[v]``` (the graph is undirected).
* The graph may not be connected, meaning there may be two nodes ```u``` and ```v``` such that there is no path between them.

A graph is **bipartite** if the nodes can be partitioned into two independent sets ```A``` and ```B``` such that **every** edge in the graph connects a node in set ```A``` and a node in set ```B```.

Return ```true``` if and only if it is **bipartite**.

![](https://i.imgur.com/Srtcgkw.png)
![](https://i.imgur.com/Z6WE7i1.png)


## 解題想法:
* 此題為判斷給定的圖是否為二分圖(Bipartite)
    * Bipartite: 兩個set彼此互相connect 但是自己set內部彼此不connect
    * 此題的graph[i]表示: 頂點i所有相鄰的頂點
* 想法: 用顏色判斷
    * 初始工具:
        * visited紀錄顏色
            * **0**:未拜訪 **1**:blue **2**:red 
            * visited=[0] * len(graph) 
    * 迴圈遍歷所有node: for i in range(len(graph))
        * 因為題目說不一定所有點都connect，所以要全部跑一次 
    * if判斷: 該點(i)尚未拜訪過
        * visited[i]改為1: 放入blue集合
        * que用已紀錄該點鄰居狀況: que=[i]
    * BFS判斷:
        * 每次pop出判斷當前node的鄰居
        * case1:
            * 若鄰居已拜訪過，查看是否相同顏色，若同則return False
        * case2:
            * 若鄰居尚未拜訪，給予其新顏色，並將鄰居加入que


## Python:
``` python=
class Solution(object):
    def isBipartite(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: bool
        """
        #Bipartite: 兩個set彼此互相connect 但是自己set內部彼此不connect
        #visited紀錄顏色:
        #0:未拜訪 1:blue 2:red
        visited=[0]*len(graph) 
        for i in range(len(graph)): #因為題目說不一定所有點都connect 所以要全部跑一次 
            #該點尚未拜訪過
            if visited[i]==0:
                visited[i]=1 #放入blue集合
                que=[i]
                #bfs
                while que:
                    cur_node=que.pop(0)
                    #判斷當前node的鄰居
                    for neiber in graph[cur_node]:
                        if visited[neiber]!=0: #若鄰居已經拜訪過
                            #查看是否同顏色
                            if visited[neiber]==visited[cur_node]:
                                return False
                        else: #若鄰居沒拜訪過 給予新顏色
                            visited[neiber]=2 if visited[cur_node]==1 else 1
                            que.append(neiber)
        return True

graph = [[1,3],[0,2],[1,3],[0,2]]
result=Solution()
ans=result.isBipartite(graph)
print(ans)
```

## C++:
``` cpp=
#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n=graph.size();
        vector<int> visited(n, 0); //0: unknown 1:blueSet 2:redSet
        for (int i=0; i<n; i++){
            if (visited[i]==0){
                visited[i]=1; //to blue set
                queue<int> que;
                que.push(i);
                //bfs
                while (!que.empty()){
                    int curNode=que.front(); que.pop();
                    for (auto neighber: graph[curNode]){
                        if (visited[neighber]!=0){  //already visited and same color
                            if (visited[neighber]==visited[curNode]) return false;
                        }
                        else{
                            visited[neighber] = (visited[curNode]==2)? 1 : 2;
                            que.push(neighber);
                        }
                    }
                }
            }
        }
        return true;
    }
};
```