###### 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**.


## 解題想法:
* 此題為判斷給定的圖是否為二分圖(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:

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++:

#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;
    }
};