---
# System prepended metadata

title: 886. Possible Bipartition
tags: [bfs, Leetcode, medium, python, union find, c++, graph]

---

###### 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:
``` 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++:
``` cpp=
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;
    }
};
```