Possible Bipartition

Problem Statement

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.

Leetcode Link

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:

• 1 <= n <= 2000
• 0 <= dislikes.length <= 10⁴
• dislikes[i].length == 2
• 1 <= dislikes[i][j] <= n
• a_i < b_i
• All the pairs of dislikes are unique.

Code

Python Code

class Solution(object):
    def possibleBipartition(self, N, dislikes):
        """
        :type N: int
        :type dislikes: List[List[int]]
        :rtype: bool
        """
        graph = collections.defaultdict(list)

        for d in dislikes:
            graph[d[0]].append(d[1])
            graph[d[1]].append(d[0])

        # print graph
        def dfs(node,graph,color):
            for nei in graph[node]:
                if color[nei-1]!=float('inf'):
                    if color[nei-1]==color[node-1]:
                        return False
                    else:
                        continue
                else:
                    color[nei-1]=color[node-1]*-1
                    if not dfs(nei,graph,color):
                        return False

            return True


        color = [float('inf') for i in range(N)]
        color[0]=1
        return dfs(1,graph,color)