LeetCode 솔루션 분류
[12/21] 886. Possible Bipartition
본문
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
Constraints:
- <li style="border: 0px solid; box-sizing: border-box; --tw-border-spacing-x:0; --tw-border-spacing-y:0; --tw-translate-x:0; --tw-translate-
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
from collections import defaultdict
class Solution:
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
if n == 1 or not dislikes: return True
NO_COLOR, RED, BLUE = 0,1,-1
color_map = defaultdict(int)
dislike_map = defaultdict(list)
for p1, p2 in dislikes:
dislike_map[p1].append(p2)
dislike_map[p2].append(p1)
def dfs(person, color):
color_map[person] = color
for xlikep in dislike_map[person]:
if color_map[xlikep] == color: return False
if color_map[xlikep] == NO_COLOR and not dfs(xlikep, -color): return False
return True
for person in range(1, n+1):
if color_map[person] == NO_COLOR and not dfs(person, RED):
return False
return True
