886. Possible Bipartition (Depth-First Search, Breadth-First Search, Union Find, Graph)

링크 - https://leetcode.com/problems/possible-bipartition/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-thirty-days

난이도 - Medium

Intuition

우리는 BFS를 통해 이 문제를 풀 수 있다. 먼저 모든 노드들의 색깔을 -1로 설정한다. 그리고 dislikes를 통해 graph를 만들어주고, bfs를 통해 인접한 노드들이 같은 색깔을 가지는지를 확인한다. 만약 같은 색깔일 경우, 서로 싫어하는 사람들끼리 같은 팀에 있다는 뜻이므로 False를 반환해야 한다.

Code

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        graph = [[] for _ in range(n+1)]
        for dislike in dislikes:
            graph[dislike[0]].append(dislike[1])
            graph[dislike[1]].append(dislike[0])

        def bfs(source):
            queue = deque([source])
            color[source] = 0 # Start with marking source as 'RED'
            while queue:
                node = queue.popleft()
                for neighbor in graph[node]:
                    # If there is a conflict, return false.
                    if color[neighbor] == color[node]:
                        return False
                    if color[neighbor] == -1:
                        color[neighbor] = 1 - color[node]
                        queue.append(neighbor)
            return True

        # 0 stands for red and 1 stands for blue.
        color = [-1] * (n+1)
        for i in range(1, n+1):
            if color[i] == -1:
                # For each pending component, run BFS.
                if not bfs(i):
                    # Return false, if there is conflict in the component.
                    return False

        return True

Complexity

여기서 E는 dislikes의 len이고, N은 사람들의 개수이다.

Time Complexity: O(N + E) 모든 노드들은 Queue에 한번씩 올라가기 때문에 N만큼 소요가 된다. 우리는 또한 모든 노드들에 대해서 edge를 탐험하므로 O(E)가 추가된다. 

Space Complexity: O(N + E) Worst scenario에서 queue는 N만큼 증가될 수 있다. 우리는 또한 graph에 E만큼, color에 N만큼 공간을 소요한다.