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

# 886. Possible Bipartition

## [題目連結:] https://leetcode.com/problems/possible-bipartition/description/

## 題目:
We want to split a group of ```n``` people (labeled from ```1``` to ```n```) into two groups of **any size**. Each person may dislike some other people, and they should not go into the same group.

Given the integer n and the array ```dislikes``` where ```dislikes[i] = [ai, bi]``` indicates that the person labeled ```ai``` does not like the person labeled ```bi```, return ```true``` if it is possible to split everyone into two groups in this way.

**Example 1:**

Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4] and group2 [2,3].

**Example 2:**

Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false

**Example 3:**

Input: n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false

## 解題想法:
* 此題為二分圖: 相鄰的兩點不能為同個群組
* 使用BFS拜訪:
* 進行顏色判別:
* 0: Unknown
* 1: visited First Group
* 2: visited Second Group
* 流程:
* Step1:
* 建立雙向邊 graph
* visited=[0]* (n+1)
* visited[i]對應i person
* Step2:
* for i in range(1,n+1) #因為題目說1~n，並非從0開始
* 若visited[i]=0: 才進行後續Step3判斷
* Step3:
* 將當前visited[i]=1
* que=[i] #紀錄此位置
* Step4:
* while que:
* 當前que中的node=curPos
* 判斷curPos的鄰居是否進行著色:
* 若visited[neighber]==0:
* 填入與visited[curPos]的顏色
* **que.append(neighber)**
* 否則若與visited[curPos]相同:
* return False

## Python:

from collections import defaultdict
class Solution(object):
    def possibleBipartition(self, n, dislikes):
        """
        :type n: int
        :type dislikes: List[List[int]]
        :rtype: bool
        """
        #對每點進行渲染:
        #0: UnKnown 1、2: visited
        #若相鄰的衝突 則為false
        graph=defaultdict(list)
        for u,v in dislikes:
            graph[u].append(v)
            graph[v].append(u)
        visited=[0]*(n+1) #v[i]對應i person
        for i in range(1,n+1):
            if visited[i]==0: #尚未拜訪
                visited[i]=1 #設為1
                que=[i]
                while que:
                    curPos=que.pop(0)
                    for neighber in graph[curPos]:
                        if visited[neighber]==0: #鄰居填入不同顏色
                            visited[neighber]=2 if visited[curPos]==1 else 1
                            que.append(neighber)
                        elif visited[neighber]==visited[curPos]:
                            return False
        return True

## C++:

class Solution {
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        unordered_map<int, vector<int>> graph;
        vector<int> visited(n+1,0);
        //connect the graph
        for (auto item: dislikes){
            graph[item[0]].push_back(item[1]);
            graph[item[1]].push_back(item[0]);
        }
        queue<int> que;
        //check neighber
        for (int i=1; i<n+1; i++){
            if (visited[i]==0){
                visited[i]=1;
                que.push(i);
                while (!que.empty()){
                    int curPos=que.front(); que.pop();
                    for (auto neighber: graph[curPos]){
                        if (visited[neighber]==0){ //paint on different color
                            visited[neighber]= (visited[curPos]==1)? 2:1;
                            que.push(neighber);
                        }
                        else if (visited[neighber]==visited[curPos]){
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
};