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

  }

}