有 N 個人(編號 1, 2, …, N)，要依照 dislikes 去分成二組，在 dislikes 中，每組 [a, b] 代表該編號的二人不能在同一組。
回傳 True 如果可以順利分成二組，否則 False。
這題蠻有意思的，我第一念頭想到 backtrace 可以硬解，但太慢，我放棄用 DP 與 遞迴函數。
說到兩兩成對，就想到最近的表格式DP，這題一樣可以用表格式DP，最後用 DFS 的遞迴函數可以比 backtrace 快上不少。
只要表格上可以選成每列每欄都只有一組配對，那就有可行的分組，也就是True。
抛開遞迴，因為平面化的話，一有答案可以馬上回傳，而遞迴函數會一路收斂到最上方，才能停止。要是深度深，會多花上一些時間。
被自我侷限，得用別的方法來。
如果 [a,b] 是 [1, 3]，代表 1, 3 不能同組。這個分組沒有順序，也就是 組1、組2 對調是沒差的。
但如果用人的思維去硬分，肯定要選一組當基準去分配，就會產生順序的問題。
[1,3],[2,4],[3,4]，答案是 True 分成 [1,4],[2,3] 。但如果都選 組1 當基準，輪到 [2,4] 分配的時候，要是組別分成 [1,2],[3,4]，
那下一個遇到分[3,4]，就會無法依規則分，然後回傳 False 。
要是換個順序 [1,3],[3,4],[2,4]，選基準去分，就會得到一組可行的，回傳 True。
[1,3] 後面接 [3,4] ，頭尾相接，可以想是一條討厭鏈，不同討厭鏈之間任意分配是沒關係的，但在同一條就該按順序來，如果可以串起來，就該優先分配。
依題目所限，dislikes 已經有排列過，所會先拿到討厭鏈的頭，想辦法後面依序先分配。
如果開頭是 [1,3] ，下一個要以 3 為開頭，[3, 4]，再以 4 開頭，再以 2 開頭，這不是一個有固定順序的，但要把 N 個開頭都找過。
討厭鏈一定要順利分完，依討厭鏈去分配是很簡單的，二人不要在同一組，分不下去就一定是回傳 False。
首先全部人都先在 組1 ，如果 [a, b] 都在 組1，把 b 移到 組2。如果 [a,b] 都在 組2 ，即無法分，回傳 False。
(用這思考看看：N = 3, dislikes = [[1,2],[1,3],[2,3]])
要依照討厭鏈順序去分的方法︰
用一個 set(1,2,…,N) ，跟 stack，遇到數字就從 set 中取到 stack。若 stack 為空，就從 set 任取一個放入stack，直到把 set 取光。
Python
class Solution:
def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
memo = defaultdict(list)
for me, you in dislikes:
memo[me].append(you)
memo[you].append(me)
group1 = set(range(1,N+1))
group2 = set()
candidate = set(range(1, N+1))
stack = []
while candidate:
stack.append(candidate.pop())
while stack:
i = stack.pop(0)
for hate in memo[i]:
if i in group1 and hate in group1:
group1.discard(hate)
group2.add(hate)
elif i in group2 and hate in group2:
return False
if hate in candidate:
stack.append(hate)
candidate.discard(hate)
return True
C#
public class Solution {
public bool PossibleBipartition(int N, int[][] dislikes) {
var relation = new Dictionary>();
var group1 = new HashSet();
var group2 = new HashSet();
var candidate = new HashSet();
for(int i = 1; i <= N; i++)
{
relation[i] = new HashSet();
group1.Add(i);
candidate.Add(i);
}
for(int i = 0; i < dislikes.Length; i++)
{
relation[dislikes[i][0]].Add(dislikes[i][1]);
relation[dislikes[i][1]].Add(dislikes[i][0]);
}
var queue = new Queue();
while(candidate.Count > 0)
{
queue.Enqueue(candidate.First());
candidate.Remove(candidate.First());
while(queue.Count > 0)
{
int head = queue.Dequeue();
foreach(int node in relation[head])
{
if(group1.Contains(head) && group1.Contains(node))
{
group1.Remove(node);
group2.Add(node);
}
else if(group2.Contains(head) && group2.Contains(node))
{
return false;
}
if(candidate.Contains(node))
{
candidate.Remove(node);
queue.Enqueue(node);
}
}
}
}
return true;
}
}