Possible Bipartition

Given a set ofN people (numbered1, 2, ..., N), we would like to split everyone into two groups ofanysize.

Each person may dislike some other people, and they should not go into the same group.

Formally, ifdislikes[i] = [a, b], it means it is not allowed to put the people numberedaandbinto the same group.

Returntrue if and only if it is possible to split everyone into two groups in this way.

1. Example 1:

Input: 
N = 
4
, dislikes = 
[[1,2],[1,3],[2,4]]
Output: 
true
Explanation
: group1 [1,4], 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

Note:

1 <= N <= 2000
0 <= dislikes.length <= 10000
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
There does not exist i != j for which dislikes[i] == dislikes[j].

分析

和以往visit直接返回不同，这里visit的话就判断对错返回，否则继续bfs或者dfs

color既记录颜色（0，1），也当做seen用。每次dfs比较颜色，不对就返错。记得main里要loop 防止没有遍历过的人。

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        mm = collections.defaultdict(list)
        for a,b in dislikes:
            mm[a].append(b)
            mm[b].append(a)

        color = {}
        def dfs(i,g):
            if i in color:
                return True if color[i] == g else False            
            color[i] = g
            for j in mm[i]:                
                if not dfs(j,1-g): return False
            return True

        for i in range(N):
            if i not in color and not dfs(i,0):
                    return False
        return True

bfs:

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        mm = collections.defaultdict(list)
        for a,b in dislikes:
            mm[a].append(b)
            mm[b].append(a)

        color = {}
        def bfs(i):
            q = [i] 
            color[i] = 0
            while q:
                cur=q.pop(0)

                for j in mm[cur]:
                    if j in color:
                        if color[cur] == color[j]:
                            return False
                    else:
                        q.append(j)
                        color[j] = 1-color[cur]
            return True
        for i in range(N):
            if i not in color and not bfs(i):
                return False
        return True

union find

每次u和neighbor v 比较，一个爹就错，然后把所有Neighbor都Union。

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        mm = collections.defaultdict(list)
        for a,b in dislikes:
            mm[a].append(b)
            mm[b].append(a)
        f = [i for i in range(1,N+1)]
        def find(x):
            if f[x-1] == x:
                return x
            f[x-1] = find(f[x-1])
            return f[x-1]

        for i in range(1,N+1):
            if i in mm:
                p1 = find(i)
                p2 = find(mm[i][0])
                if p1 == p2:
                    return False
                for j in mm[i][1:]:
                    p3 = find(j)
                    if p1 == p3:
                        return False
                    f[p3-1] = p2




        return True