785, is graph bipartite

785, is graph bipartite

====

coloring,

bipartition,

BFS

====

1. 同886, 給予一個vec<vec<int>>graph

限制不同屬的規則(dislike)

新增一個vec<int>color

0初值, 1,-1兩類

新增一個queue q處理每次的相關元素

2. while(!q.empty) 檢查所有元素規則

for cur, 當次元素

for nei, cur元素的graph規則

如果color[nei] != 0則skip

如果color[nei]=0, 未走訪 => 看color[nei] 與color[cur]

分兩類

如果分不了兩類, false

如果走完, q空都沒有failed, 則true

====

class Solution {

public:

  bool isBipartite(vec<vec<int>>&graph) {

    int n= graph.size()

    vec<int> color(n,0)

    queue<int> q

    for(int i=0, i<n, i++){

      if(color[i] != 0)

        continue

      color[i]=1

      for( q.push(i), !q.empty(), q.pop()) {

//這種寫法？！

        int cur=q.front()

        for( int nei: graph[cur]) {

          if(color[nei] == 0) {

            q.push(nei)

            color[nei] = color[cur]==1 ? -1 : 1

          }

          if(color[nei] == color[cur])

            return false

        }//graph[cur].size

      }//!q.empty()

    }//for n

    return true

  }

}