LeetCode 솔루션

[12/21] 886. Possible Bipartition

학부유학생 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.12.21 07:12

11,251 조회
1 댓글
0 추천
0 비추천
목록 게시글 쓰기

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-

#Bytedance, #Tiktok, #DoorDash

링크

https://leetcode.com/problems/possible-bipartition/description/ 2130 회 연결

익명
작성일 2022.12.21 07:12

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