886. Possible Bipartition

Stanislav Gumeniuk включен в leetcode leetcode-problem

2020.05.27 357 слов Пару мгновений

Содержание

Условие задачи

Дан набор из Nлюдей (все пронумерованы 1,2, … , N), мы хотим разделить этих людей на две группы.

Каждый человек может не любить другого человека, и такие люди долджны быть в разных группах.

dislikes[i] = [a, b] – означатет что нельзя человека aи b поместить в одну группу.

Необходимо вернуть true если такое разбиение возможно.

пример 1

1
2
3


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

пример 2

1
2


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

пример 3

1
2


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

пример 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

Ограничения

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

Решение

Hash map + DFS

Создаем мапу, где ключом будет id человека,а значение – массив людей, котороые ему не нравятся. Обойдем весь массив дизлайков и запишем дизлайки в мапу, но запишем в каждую сторонут, то есть когда мы встретим дизлайк [3,5] - мы запишем, что третьему не нравится пятый , и что пятому не нравится третий. ( то есть m[3]=[...,5,...] и m[5]=[...,3,...]).

И дальше поиск в глубину

 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
}