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

  }

}

886, possible bipartition

886, possible bipartition

====

Coloring

Bipartition

====

1. 與union類似（？

給予一個vec<vec<int>> dislike的rule, 跟N個元素

->

新增一個vec<vec<int>> graph, 紀錄需要走訪的關係

//類似於union的input

新增一個color(N, 0)

0未走訪, 1,2兩類

新增一個queue處理當次graph元素的所有關係

//?

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

for u, 當次元素

for v, u元素的graph規則

如果color[v] != 0則skip

如果color[v]=0, 未走訪 => 看color[u] 與color[v]

分兩類

如果分不了兩類, false

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

====

class Solution {

public:

  bool possibleBipartition(int N, vec<vec<int>&dislike) {

  vec<vec<int>>graph(N, vec<int>())

  queue<int> q

  vec<int> color(N, 0)

  for( i=0, i< dislike.size(), i++ ){

    u= graph[i][0] -1

    v= graph[i][1] -1

    graph[u].push_back(v)

    graph[v].push_back(u)

  }

  for( i=0, i<N, i++){

    if(color[i] != 0)

      continue

    q.push(i)

    color[i]=1 //起始

    while( !q.empty() ){

      u= q.front()

      q.pop()

      for( k=0, k<graph[u].size, k++ ){

        v= graph[u][k]

        if(color[v]==0){

          q.push(v)

          color[v] = color[u]==1 ? 2 : 1

        }

        if(color[v]==color[u])

          return false

      }//for graph[u].size

      

    }//while

  }//for N

  return true

  }

}