Catalog

1. Problem description

2. Problem solving analysis

2.1 Train of thought

2.2 Train of thought two

2.3 Train of thought three ： To color + Depth-first search

3. Code implementation

---

1. Problem description

Give a group  n  people （ The number is  1, 2, ..., n）,  We want to divide everyone into arbitrarily Two groups of size . Everyone may not like other people , So they shouldn't belong to the same group .

Given integer  n  And an array  dislikes , among  dislikes[i] = [ai, bi] , Indicates that numbering as... Is not allowed  ai  and   bi All the people belong to the same group . When you can divide everyone into two groups in this way , return  true; Otherwise return to  false.

Example 1：

 Input ：n = 4, dislikes = [[1,2],[1,3],[2,4]]
 Output ：true
 explain ：group1 [1,4], 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

Tips ：

• 1 <= n <= 2000
• 0 <= dislikes.length <= 10^4
• dislikes[i].length == 2
• 1 <= dislikes[i][j] <= n
• ai < bi
• dislikes  Each group in the group   Different

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/possible-bipartition
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

2. Problem solving analysis

2.1 Train of thought

   dislikes Representing a graph edges The list represents , Let's call this picture dislike-graph.

        A simple idea , Build the complement of this graph like-graph, Then check the supplementary drawing like-graph Is the number of connected subgraphs less than or equal to 2. In supplementary drawing like-graph in , The nodes in two different connected subgraphs are obviously mutual dislike Of . So if like-graph The number of connected subgraphs exceeds 2 individual , Can't be divided into 2 A group , Make sure there is no mutual dislike People who . And if the like-graph The number of connected subgraphs is equal to 2, The node set contained in these two subgraphs is the only grouping method to meet the meaning of the question . If like-graph The number of connected subgraphs is equal to 1（ That is, the whole connection diagram ）, Then you can divide it arbitrarily .

        Of course , This like-graph There is no need to explicitly create .

        Just create dislike-graph Adjacency list of （ establish like-graph The adjacency list is better than creating dislike-graph The adjacency list is troublesome , Large storage requirements ）, Then based on dislike-graph The adjacency list of like-graph Traversal of , Breadth first search or depth first search .

        But I drew pictures , From example 3 I find that the above idea is not correct .

2.2 Train of thought two

        In fact, this problem is equivalent to looking for this dislike-graph Whether there is a ring composed of an odd number of nodes in .

        (1) If there is a ring composed of an odd number of nodes , It's impossible to divide them into two groups and avoid people who don't like being divided into one group . This is obvious .

        (2) When there is no ring composed of odd nodes , Can they be divided into two groups that meet the conditions ？

        Let's assume that the above idea is true （ It doesn't seem to be an easy thing to prove ）.

        Starting from any node , Path traversal of the graph , If the newly explored node on a path already exists on the path , It means finding a loop . After finding the loop, check the length of the loop .

        then , Repeat the above process , Until the traversal of the whole graph is completed .

        If you find a ring with an odd length, you can exit and return False. If no ring of odd length is found, return True.

        however , Search for a path , Is to find a ring and quit , Or keep searching ？ Neither seems to work .

        Uh ... This road seems to be impassable

        

2.3 Train of thought three ： To color + Depth-first search

         Try to assign everyone to one of two groups . Suppose the people in the first group are red , The people in the second group are blue .

         If the first person is red , Then the person you don't like must be blue . then , Anyone who doesn't like blue people is red , So anyone who doesn't like red people is blue , And so on . If there is a conflict at any time , Then this task is impossible to complete , Because from the first step, every step is logical . If there is no conflict , So coloring is effective , It shows that it is feasible to divide into two groups .

        Consider by N Made up of individuals dislike-graph,dislikes The array represents the change of the graph edge list.

        Based on the above ideas , We need to check whether each connected branch of the graph is a bipartite graph .

         For each connected part , We just try to color it with two colors , You can check whether it is binary . You can do depth first search as follows （ The search of this question is related to the path , You can't use breadth first search ）：

1.          Color any node red , Then paint all its neighbors blue , Then paint all the neighbors' neighbors red , And so on . If the search process finds that a node ready to be painted blue has been painted red before （ Or vice versa ） It shows that there is a conflict , Grouping cannot be established , The end of the search .
2.         After the above traversal , Start a new traversal by selecting any one of the remaining uncolored nodes .
3.         Repeat the above steps 2 Until all nodes are colored （ To be accessed ）, Or withdraw early due to conflict .

        

3. Code implementation

import time
from typing import List
from collections import deque

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        if n == 1:
            return True
        # construct adjacency list
        adjlist = [[] for k in range(n+1)]
        for dislike in dislikes:
            adjlist[dislike[0]].append(dislike[1])
            adjlist[dislike[1]].append(dislike[0])
            
        color = (n+1) * [-1]
        for k in range(1,n+1):
            if color[k] < 0:
                q = deque([k])
                color[k] = 0
                while len(q)>0:
                    node = q.pop()
                    for adj in adjlist[node]:
                        if color[adj] < 0:
                            color[adj] = 1 - color[node]
                            q.append(adj)
                        else:
                            if color[adj] == color[node]:
                                return False
        return True
                    
if __name__ == "__main__":
    
    sln = Solution()
    
    n = 4
    dislikes = [[1,2],[1,3],[2,4]]
    print(sln.possibleBipartition(n, dislikes))
    
    n = 3
    dislikes = [[1,2],[1,3],[2,3]]
    print(sln.possibleBipartition(n, dislikes))
    
    n = 5
    dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
    print(sln.possibleBipartition(n, dislikes))

         Execution time ：108 ms, In all  Python3  Defeated in submission 91.64% Users of

         Memory consumption ：18.4 MB, In all  Python3  Defeated in submission 89.10% Users of

          Um. , Can perform well in both time and memory , It's worth a little pride .

        Spit a small slot ：n=1 When you press leetcode Your feedback should go back to True, But this is actually a question of definition .leetcode Take this as a testcase A little boring . It's better to define n>=2 Isn't it more refreshing .

        Go back to the general catalogue ：  Slow ploughing by stupid cattle Leetcode General catalogue of daily questions ( Dynamic update ...)