Contents

# Problem

Given a set of `N` people (numbered 1, 2, …, `N`), we would like to split everyone into two groups of any size.

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

Formally, if `dislikes[i] = [a, b]`, it means it is not allowed to put the people numbered `a` and `b` into the same group.

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

## example 1

 ``````1 2 3 `````` ``````Input: N = 4, dislikes = [[1,2],[1,3],[2,4]] Output: true Explanation: group1 [1,4], group2 [2,3] ``````

## example 2

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

## example 3

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

## example 4

 ``````1 2 `````` ``````Input: N = 10, dislikes = [[4,7],[4,8],[5,6],[1,6],[3,7],[2,5],[5,8],[1,2],[4,9],[6,10],[8,10],[3,6],[2,10],[9,10],[3,9],[2,3],[1,9],[4,6],[5,7],[3,8],[1,8],[1,7],[2,4]] Output: true ``````

## Constraints

• 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]`.

# Solution

## Hash map + DFS

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 `````` ``````func possibleBipartition(N int, dislikes [][]int) bool { m := make(map[int][]int, N+1) c := make(map[int]int, N+1) for idx := range dislikes { if _, ok := m[dislikes[idx][0]]; !ok { m[dislikes[idx][0]] = make([]int, 0) } m[dislikes[idx][0]] = append(m[dislikes[idx][0]], dislikes[idx][1]) m[dislikes[idx][1]] = append(m[dislikes[idx][1]], dislikes[idx][0]) } for idx := range m { if _, ok := c[idx]; !ok && !clr(m, c, idx, 0) { return false } } return true } func clr(m map[int][]int, c map[int]int, i, color int) bool { if _, ok := c[i]; ok { return c[i] == color } c[i] = color for idx := range m[i] { if !clr(m, c, m[i][idx], color^1) { return false } } return true } ``````