Debugging the solution to a possible Bipartition

Question

I came across this problem

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

Below is my approach to the solution:

1. create two lists, group1 and group2 and initialise group1 with 1
2. generate all the numbers from 2 to n in a variable called num
3. check if num is enemy with group1 elements, if yes, then check if num is enemy with group2 elements, if yes as well, return False
4. else put num in its respective group and goto step 2 with the next value
5. return True

below is the code implementation

class Solution(object):
    def possibleBipartition(self, n, dislikes):
        """
        :type n: int
        :type dislikes: List[List[int]]
        :rtype: bool
        """

        group1 = [1]
        group2 = []
    
        for num in range(2, n+1):

            put_to_group_1 = 1
            for _n in group1:
                if [_n, num] in dislikes or [num, _n] in dislikes:
                    put_to_group_1 = 0
                    break
        
            put_to_group_2 = 1
            for _n in group2:
                if[_n, num] in dislikes or [num, _n] in dislikes:
                    put_to_group_2 = 0
                    break
        
            if put_to_group_1 == 0 and put_to_group_2 == 0:
                return False

            if put_to_group_1 == 1:
                group1.append(num)
            else:
                group2.append(num)

        return True

However for the following input I am getting False, but the expected output isTrue.

50
[[21,47],[4,41],[2,41],[36,42],[32,45],[26,28],[32,44],[5,41],[29,44],[10,46],[1,6],[7,42],[46,49],[17,46],[32,35],[11,48],[37,48],[37,43],[8,41],[16,22],[41,43],[11,27],[22,44],[22,28],[18,37],[5,11],[18,46],[22,48],[1,17],[2,32],[21,37],[7,22],[23,41],[30,39],[6,41],[10,22],[36,41],[22,25],[1,12],[2,11],[45,46],[2,22],[1,38],[47,50],[11,15],[2,37],[1,43],[30,45],[4,32],[28,37],[1,21],[23,37],[5,37],[29,40],[6,42],[3,11],[40,42],[26,49],[41,50],[13,41],[20,47],[15,26],[47,49],[5,30],[4,42],[10,30],[6,29],[20,42],[4,37],[28,42],[1,16],[8,32],[16,29],[31,47],[15,47],[1,5],[7,37],[14,47],[30,48],[1,10],[26,43],[15,46],[42,45],[18,42],[25,42],[38,41],[32,39],[6,30],[29,33],[34,37],[26,38],[3,22],[18,47],[42,48],[22,49],[26,34],[22,36],[29,36],[11,25],[41,44],[6,46],[13,22],[11,16],[10,37],[42,43],[12,32],[1,48],[26,40],[22,50],[17,26],[4,22],[11,14],[26,39],[7,11],[23,26],[1,20],[32,33],[30,33],[1,25],[2,30],[2,46],[26,45],[47,48],[5,29],[3,37],[22,34],[20,22],[9,47],[1,4],[36,46],[30,49],[1,9],[3,26],[25,41],[14,29],[1,35],[23,42],[21,32],[24,46],[3,32],[9,42],[33,37],[7,30],[29,45],[27,30],[1,7],[33,42],[17,47],[12,47],[19,41],[3,42],[24,26],[20,29],[11,23],[22,40],[9,37],[31,32],[23,46],[11,38],[27,29],[17,37],[23,30],[14,42],[28,30],[29,31],[1,8],[1,36],[42,50],[21,41],[11,18],[39,41],[32,34],[6,37],[30,38],[21,46],[16,37],[22,24],[17,32],[23,29],[3,30],[8,30],[41,48],[1,39],[8,47],[30,44],[9,46],[22,45],[7,26],[35,42],[1,27],[17,30],[20,46],[18,29],[3,29],[4,30],[3,46]]

Can anyone tell me where I might be going wrong with the implementation?

Answer 1

Consider a scenario:

1. Let's assume that in the dislikes array, we have [1,6],[2,6] among other elements (so 6 hates 1 and 2).
2. Person 1 doesn't hate anybody else
3. After placing everybody into groups, let's say 2 gets placed in group 2.
4. While placing 6, you can't put it in either group, since it conflicts with 1 in group 1 and 2 in group 2.
5. 6 could have been placed in group 1 if you didn't start with the assumption of placing 1 in group 1 (ideally 1 could have been placed in group 2 without conflict).

Long story short, don't start with person 1 in group 1. Take the first element in the dislikes array, put either of them in either group, and then continue with the algorithm.