Catalog

1. Problem description

2. Problem solving analysis

3. Code implementation

---

1. Problem description

There is one.   Undirected graph  , The picture shows  n  Nodes . Each of these nodes has a value between  0  To  n - 1  Unique number between . Give you a two-dimensional array  graph , among  graph[u]  Is an array of nodes , By nodes  u  Consists of adjacent nodes . Formally , about  graph[u]  Each of the  v , There is one at node  u  And nodes  v  The undirected edge between . The undirected graph also has the following properties ：

• There is no self ring （graph[u]  It doesn't contain  u）.
• There are no parallel edges （graph[u]  Does not contain duplicate values ）.
• If  v  stay  graph[u]  Inside , that  u  It should be in  graph[v]  Inside （ The graph is undirected ）
• This graph may not be a connected graph , That is, two nodes  u  and  v  There may not be a path connecting each other .

Bipartite graph   Definition ： If the node set of a graph can be divided into two independent subsets  A  and  B , And make one of the two nodes of each edge in the graph come from  A  aggregate , One from  B  aggregate , This graph is called   Bipartite graph  .

If the graph is bipartite , return  true ; otherwise , return  false .

Example 1：

 Input ：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
 Output ：false
 explain ： Nodes cannot be divided into two independent subsets , So that each edge connects a node in one subset with a node in another subset .

Example 2：

 Input ：graph = [[1,3],[0,2],[1,3],[0,2]]
 Output ：true
 explain ： Nodes can be divided into two groups : {0, 2}  and  {1, 3} .

Tips ：

• graph.length == n
• 1 <= n <= 100
• 0 <= graph[u].length < n
• 0 <= graph[u][i] <= n - 1
• graph[u]  Will not contain  u
• graph[u]  All values   Different from each other
• If  graph[u]  contain  v, that  graph[v]  It will also include  u

 

2. Problem solving analysis

         This problem is the same as the previous one in this series of basic topics of graph theory leetcode886 Just change the soup without changing the dressing .

        But what this question gives directly is the adjacency table （adjacency list）, and leetcode886 Given dislikes It stands for edge list .

         Please refer to... For specific solutions leetcode886 (Leetcode0886. Possible dichotomy (medium, Bipartite graph )).

3. Code implementation

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:

        n = len(graph)
        if n == 1:
            return True
            
        color = (n) * [-1]
        for k in range(n):
            if color[k] < 0:
                q = deque([k])
                color[k] = 0
                while len(q)>0:
                    node = q.pop()
                    for adj in graph[node]:
                        if color[adj] < 0:
                            color[adj] = 1 - color[node]
                            q.append(adj)
                        else:
                            if color[adj] == color[node]:
                                return False
        return True

 

         Execution time ：32 ms, In all  Python3  Defeated in submission 98.25% Users of

         Memory consumption ：15.3 MB, In all  Python3  Defeated in submission 77.72% Users of

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