【Day 30 】2022-01-10 - 886. 可能的二分法

[azl397985856]

886. 可能的二分法

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/possible-bipartition/

前置知识

• 图的遍历
• DFS

  题目描述

  
  给定一组 N 人（编号为 1, 2, ..., N）， 我们想把每个人分进任意大小的两组。

每个人都可能不喜欢其他人，那么他们不应该属于同一组。

形式上，如果 dislikes[i] = [a, b]，表示不允许将编号为 a 和 b 的人归入同一组。

当可以用这种方法将每个人分进两组时，返回 true；否则返回 false。

 

示例 1：

输入：N = 4, dislikes = [[1,2],[1,3],[2,4]] 输出：true 解释：group1 [1,4], group2 [2,3] 示例 2：

输入：N = 3, dislikes = [[1,2],[1,3],[2,3]] 输出：false 示例 3：

输入：N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]] 输出：false  

提示：

1 <= N <= 2000 0 <= dislikes.length <= 10000 dislikes[i].length == 2 1 <= dislikes[i][j] <= N dislikes[i][0] < dislikes[i][1] 对于dislikes[i] == dislikes[j] 不存在 i != j

[yan0327]

思路： 三色标记法+BFS系列 构造邻接图,BFS找答案

func possibleBipartition(n int, dislikes [][]int) bool {
    graph := make([][]int,n+1)
    for _,v := range dislikes{
        graph[v[0]] = append(graph[v[0]],v[1])
        graph[v[1]] = append(graph[v[1]],v[0])
    }
    color := make([]int,n+1)
    for i:=1;i<n+1;i++{
        if color[i] != 0{
            continue
        }
        color[i] = 1
        queue := []int{i}
        for len(queue) != 0{
            node := queue[0]
            queue = queue[1:]
            for _,v := range graph[node]{
                if color[v] == color[node]{
                    return false
                }
                if color[v] != 0{
                    continue
                }
                queue = append(queue,v)
                if color[v] == 0{
                    color[v] = -color[node]
                }
            }
        }
    }
    return true
}

时间复杂度：O（N+E） 空间复杂度：O（N+E）

[yetfan]

思路 相连接点不同着色，dfs进行检验冲突

代码

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        graph = collections.defaultdict(list)
        for a, b in dislikes:
            graph[a].append(b)
            graph[b].append(a)

        colour = {}
        def dfs(node, c=0):
            if node in colour:
                return colour[node] == c
            colour[node] = c

            for neiberhood in graph[node]:
                if not dfs(neiberhood, c ^ 1):
                    return False
            return True

        for node in range(1, n+1):
            if node not in colour and not dfs(node):
                return False
        return True

复杂度 时间 O(n+e) 空间 O(n+e)

[tian-pengfei]

class Solution {
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {

        if(dislikes.size()==0)return true;
//
//        [[],[a,b,c]] 1不喜欢的节点为 a,b,c。i坐标代表节点，只为不喜欢的节点
        vector<vector<int>> gra(n+1,vector<int>());

//        记录节点分组情况 -1未分组，0为0组 1为1组
            vector<int> group(n+1,-1);

            for(auto &dislike:dislikes){
                gra[dislike[0]].push_back(dislike[1]);
                gra[dislike[1]].push_back(dislike[0]);
            }

            for(int i=1;i<=n;i++){
                if(group[i]==-1){
                    if(!dfs(gra,group,i,0))return false;
                }
            }

            return true;

    }

//   dfs的形式分组，当分组冲突时返回false;

    bool  dfs( vector<vector<int>>& gra,vector<int> &group,int i,int g){

        if(group[i]!=-1){
            return group[i]==g;
        }

        group[i]=g;
        for(auto & j:gra[i]){
            if(!dfs(gra,group,j,g^1))return false;
        }

        return true;

    }
};

[BpointA]

思路

上色+dfs

代码

class Solution {
    int [] colors;
    HashMap<Integer,List<Integer>> tmp;
   public boolean ccc(int node,int c)
        {
            this.colors[node]=c;
            List<Integer> tt=this.tmp.getOrDefault(node,new ArrayList<Integer>());
            for(int k1=0;k1<tt.size();k1++)
            {
                int k=tt.get(k1);
                if(this.colors[k]==c)
                {return false;}
                else if(this.colors[k]==3-c)
                {continue;}
                else
                {
                    if(ccc(k,3-c)==false)
                    {
                        return false;
                    }
                }
            }
            return true;
        }
    public boolean possibleBipartition(int n, int[][] dislikes) {
        this.colors=new int[n];
        this.tmp=new HashMap<>();
        for (int[] i : dislikes)
        {
            List<Integer> t1=this.tmp.getOrDefault(i[0]-1,new ArrayList<Integer>());
            t1.add(i[1]-1);
            this.tmp.put(i[0]-1,t1);
            List<Integer> t2=this.tmp.getOrDefault(i[1]-1,new ArrayList<Integer>());
            t2.add(i[0]-1);
            this.tmp.put(i[1]-1,t2);
        }
        for (int node=0;node<n;node++)
        {
            if(this.colors[node]>0)
            {continue;}
            if (!this.ccc(node,1) && !this.ccc(node,2))
            {return false;}
        }

        return true;

    }
}

[MongoCZK]

/**
 * @param {number} n
 * @param {number[][]} dislikes
 * @return {boolean}
 */
var possibleBipartition = function (n, dislikes) {
  let ok = true;
  let color = new Array(n + 1).fill(false);
  let visited = new Array(n + 1).fill(false);
  const buildGraph = (n, dislikes) => {
    let graph = new Array(n + 1).fill(0).map(() => new Array());
    for (let edge of dislikes) {
      let v = edge[1];
      let w = edge[0];
      graph[v].push(w);
      graph[w].push(v);
    }
    return graph;
  };
  const traverse = (graph, v) => {
    if (!ok) return;
    visited[v] = true;
    for (let w of graph[v]) {
      if (!visited[w]) {
        color[w] = !color[v];
        traverse(graph, w);
      } else {
        if (color[w] == color[v]) ok = false;
      }
    }
  };

  // 转化成邻接表表示图结构
  const graph = buildGraph(n, dislikes);
  for (let i = 1; i <= n; i++) {
    if (!visited[i]) traverse(graph, i);
  }
  return ok;
};

[Alfie100]

LeetCode题目连接： 886. 可能的二分法https://leetcode-cn.com/problems/possible-bipartition/

解题思路

判断是否能够形成二分图。

可参见另一道原题：LeetCode 785. 判断二分图 https://leetcode-cn.com/problems/is-graph-bipartite/

Python 代码

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:

        graph = collections.defaultdict(list)
        for u,v in dislikes:
            graph[u].append(v)
            graph[v].append(u)

        def dfs(u, c):
            if color[u] == 3-c:
                self.valid = False
                return
            elif color[u] == 0:
                color[u] = c
                for v in graph[u]:
                    dfs(v, 3-c)
                    # if not self.valid:
                    #     return

        self.valid = True
        color = [0] * (n+1)     # 0: 未着色；1：着色1；2：着色2。其中两种颜色水火不容。1+2=3

        for u in range(1, n+1):
            if color[u] == 0:
                dfs(u, 1)
                if not self.valid:
                    return False

        return True

复杂度分析

• 时间复杂度：O(n+m)，其中 n 为人数，m为构建出的图中边的数目（最快情况下可达n^2）。
• 空间复杂度：O(n)。

[Bochengwan]

思路

dfs+ 染色

代码

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        if n==1 or not dislikes:
            return True
        graph = defaultdict(list)
        for dislike in dislikes:
            graph[dislike[0]].append(dislike[1])
            graph[dislike[1]].append(dislike[0])
        colored = dict()
        def dfs(curr,curr_color):
            if curr in colored:
                if colored[curr] != curr_color:
                    return False
                else:
                    return True

            else:
                colored[curr] = curr_color
                for other in graph[curr]:
                    if not dfs(other,-curr_color):
                        return False
            return True
        for i in range(1,n+1):
            if i not in colored:

                if not dfs(i,1):
                    return False
        return True

复杂度分析

• 时间复杂度：O(N+E)，其中 N 为数组长度。
• 空间复杂度：O(N+E)

[laofuWF]

# build a graph (2-way)
# paint node by relation with 2 colors using dfs
# return false when there's confict in painting a single node

# time: O(V + E)
# space: O(V + E)

class Solution:
    def __init__(self):
        self.NOT_COLORED = 0
        self.BLUE = 1
        self.RED = -1

    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        if len(dislikes) == 0 or len(dislikes) == 1:
            return True

        graph = collections.defaultdict(list)
        colors = [self.NOT_COLORED for i in range(n + 1)]

        for x, y in dislikes:
            graph[x].append(y)
            graph[y].append(x)

        for i in range(1, n + 1):
            if colors[i] == self.NOT_COLORED and not self.dfs(colors, graph, i, self.BLUE):
                return False

        return True

    def dfs(self, colors, graph, node, color):
        enemies = graph.get(node)
        if not enemies:
            return True

        colors[node] = color
        enemy_color = self.RED if color == self.BLUE else self.BLUE

        for enemy in enemies:
            if colors[enemy] == color:
                return False

            if colors[enemy] == self.NOT_COLORED and (not self.dfs(colors, graph, enemy, enemy_color)):
                return False

        return True

[feifan-bai]

思路

1. 二分图，图的遍历问题 DFS

代码

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        in_degree = [0] * (n + 1)
        out_degree = [0] * (n + 1)
        for a, b in trust:
            in_degree[b] += 1
            out_degree[a] += 1
        for i in range(1, n + 1):
            if in_degree[i] == n - 1 and out_degree[i] == 0:
                return i
        return -1

复杂度分析

• 时间复杂度：O(V+E)
• 空间复杂度：O(V*V)

[zwmanman]

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

    graph = [[0] * n for _ in range(n)]
    colors = [0] * n

    for a, b in dislikes:
        graph[a - 1][b - 1] = 1
        graph[b - 1][a - 1] = 1

    for i in range(n):
        if colors[i] == 0 and not self.dfs(graph, colors, i, 1, n):
            return False

    return True

def dfs(self, graph, colors, i, color, n):
    colors[i] = color
    for j in range(n):
        if graph[i][j] == 1:
            if colors[j] == color:
                return False
            if colors[j] == 0 and not self.dfs(graph, colors, j, -1 * color, n):
                return False

    return True

[wangzehan123]

class Solution {
    public boolean isRobotBounded(String instructions) {

        int i=0;
        int j=0;
        int dir=1;

        for(char c : instructions.toCharArray()){  // Loop through to follow every instruction

            if(c == 'G'){
                if(dir == 1) j++;  //if direction is north, move forward
                else if(dir == 2) i++;  //if direction is East, move right
                else if(dir == 3) j--;  //if direction is South, move downward
                else i--;  //if direction is west, move West
            }
            else if(c == 'L'){  // if asked to turn left
                dir = dir == 1 ? 4 : dir-1; // subtract 1 from current direction to turn left, if  dir == 1 i.e. North, we need to turn towards west i.e. 4
            }
            else if(c == 'R'){ // if asked to turn right
                dir = dir == 4 ? 1 : dir+1;  // add 1 from current direction to turn right, if  dir == 4 i.e. West, we need to turn towards North i.e. 1
            }

        }

        return i == 0 && j == 0 || dir > 1;   // check the current position and direction and decide

    }
}

[YuyingLiu2021]

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool

        from collections import defaultdict
        graph = defaultdict(list)
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)

        color = {}
        def dfs(node, c = 0):
            if node in color:
                return color[node] == c
            color[node] = c
            return all(dfs(neib, c ^ 1) for neib in graph[node])

        return all(dfs(node) for node in range(1, n+1) if node not in color)

[MonkofEast]

886. Possible Bipartition

Click Me

Algo

1. Revise +1

Code

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        # construct adjMat
        adjMat = [[0]*n for _ in range(n)]
        for a, b in dislikes:
            adjMat[a - 1][b - 1] = 1
            adjMat[b - 1][a - 1] = 1

        # bi-colors
        colors = [0] * n # 1 for group A, -1 for group b
        for i in range(n):
            # set inital group as A, so color == 1
            if colors[i] == 0 and not self.dfs(adjMat, colors, i, 1, n): return False
        return True

    def dfs(self, graph, colors, i, color, n):
        # this dfs return whether person i and people related to it can be allocate properly
        """
        graph: adj mat
        colors: len == n
        i: person
        color: initial assignment, 1 or -1
        n: number of persons
        """
        colors[i] = color
        for j in range(n): # loop relationship between i and everyone
            # person i & person j hate each other
            if graph[i][j] == 1: 
                # if j is allocated, is it leagal?
                if colors[j] == color:
                    return False
                # if j is not allocated, can it be allocated legally?
                if colors[j] == 0 and not self.dfs(graph, colors, j, -1 * color, n):
                    return False
            # if so, then i can be allocated leagally
        return True

Comp

T: O(v+e)

S: O(v+e)

[Liuxy94]

思路

参考题解 学会了染色法

代码

class Solution:
    def dfs(self, graph, colors, i, color, N):
        colors[i] = color
        for j in range(N):
            # dislike eachother
            if graph[i][j] == 1:
                if colors[j] == color:
                    return False
                if colors[j] == 0 and not self.dfs(graph, colors, j, -1 * color, N):
                    return False
        return True

    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = [[0] * N for i in range(N)]
        colors = [0] * N
        for a, b in dislikes:
            graph[a - 1][b - 1] = 1
            graph[b - 1][a - 1] = 1
        for i in range(N):
            if colors[i] == 0 and not self.dfs(graph, colors, i, 1, N):
                return False
        return True

复杂度分析

时间复杂度： O(V+E)

空间复杂度： O(V^2)

[LannyX]

思路

染色 dfs

代码

class Solution {
    ArrayList<Integer>[] graph;
    Map<Integer, Integer> color;
    public boolean possibleBipartition(int n, int[][] dislikes) {
        //initialize new array
        graph = new ArrayList[n+1];
        for(int i = 1; i <= n; i++){
            graph[i] = new ArrayList();
        }
        for(int[] edge : dislikes){
            int a = edge[0];
            int b = edge[1];
            graph[a].add(b);
            graph[b].add(a);
        }
        color = new HashMap();
        for(int node = 1; node <= n; node++){
            if(!color.containsKey(node) && !dfs(node, 0)){
                return false;
            }
        }
        return true;
    }
    private boolean dfs(int node, int c){
        if(color.containsKey(node)){
            return color.get(node) == c;
        }
        color.put(node, c);
        for(int nei : graph[node]){
            if(!dfs(nei, c^1)){
                return false;
            }
        }
        return true;
    }
}

复杂度分析

• 时间复杂度：O(N + e)
• 空间复杂度：O(N + e)

[zhangzz2015]

思路

• 利用涂色方法，进行2分，首先进行build图，再对node进行涂色，如果当前节点是root，可任意选择颜色1或者0，其他涂色使用和parent节点相反的颜色，如果有颜色冲突则表明不能完成二分，返回false，具体实现可使用BFS或者DFS。时间复杂度为O(V+E)，空间复杂度为O(N)

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {

        vector<int> color(n, -1);

        vector<vector<int>> graph(n); 
        // build graph
        for(int i=0; i< dislikes.size(); i++ )
        {
            graph[dislikes[i][0]-1].push_back(dislikes[i][1]-1); 
            graph[dislikes[i][1]-1].push_back(dislikes[i][0]-1);             
        }
        for(int i=0; i< n; i++ )
        {
            if(color[i]==-1)
            {
                color[i] = 1;                 
                if(dfs(graph, i, color)==false)
                    return false; 
//                if(bfs(graph, i, color)==false)
//                    return false; 
            }
        }
        return true; 

    }    
    bool bfs(vector<vector<int>>& graph, int iroot, vector<int>& color)
    {

        queue<int> que; 
        que.push(iroot); 
        while(que.size())
        {
            int isize= que.size(); 
            for(int i=0; i< isize; i++)
            {
                int topNode = que.front(); 
                que.pop(); 
                int topNodeColor = color[topNode]; 
                for(int i=0; i< graph[topNode].size(); i++)
                {
                    int nextNode = graph[topNode][i]; 
                    if(color[nextNode] == -1)
                    {
                        color[nextNode] = !(topNodeColor); 
                        que.push(nextNode); 
                    }
                    else if(color[nextNode] == topNodeColor)
                    {
                        return false; 
                    }                    
                }                
            }            
        }
        return true;                 
    }

    bool dfs(vector<vector<int>>& graph, int iroot, vector<int>& color)
    {
        int top_node_color = color[iroot]; 
        for(int i=0; i< graph[iroot].size(); i++)
        {
            int next_node = graph[iroot][i];
            if(color[next_node]==-1)
            {
                color[next_node] = !(top_node_color); 
                if(dfs(graph, next_node, color)==false)
                    return false; 
            }
            else if(color[next_node] == top_node_color)
                return false;             
        }

        return true; 
    }
};

[zwang2244]

思路

graph coloring

代码

class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        // 1.construct a graph
        List<Integer>[] adj = new LinkedList[n + 1]; // adj[i] stores an arraylist of adj nodes to node i;  adj[0] is an empty linkedlist
        for(int i = 0; i< adj.length; i++){
            adj[i] = new LinkedList<Integer>();
        }
        for(int[] dislike:dislikes){
            int nodei = dislike[0];
            int nodej = dislike[1];
            adj[nodei].add(nodej);
            adj[nodej].add(nodei);
        }
        // System.out.println(adj[1].size());
        // 2. an array to store colorization
        int[] colors = new int[n+1];
        // colors[0] = -2;
        // colors[1] = 1; // color the first node to 1
//         for(int j = 1; j < colors.length; j++){
//             colors[j] = 0; // unassigned
//         }

        //for each node do a bfs to traverse the graph
        for(int v = 0; v < n + 1; v++){
            if(colors[v] != 0){
                continue; // if already colored
            }
            colors[v] = 1;

            LinkedList<Integer> queue = new LinkedList<>();
            queue.add(v);
            while(!queue.isEmpty()){
                int node = queue.poll();
                // check neightbor
                List<Integer> curr_adj = adj[node]; 
                for(int u = 0; u < curr_adj.size(); u++){
                    if(colors[curr_adj.get(u)] == colors[node]){
                        return false;
                    }
                    if(colors[curr_adj.get(u)] == 0){
                        colors[curr_adj.get(u)] = -colors[node];
                        queue.add(curr_adj.get(u));
                    } 
                }
            } 
        }
        return true;
    }
}

复杂度分析

• 时间复杂度：O(N+E)，其中 N 为数组长度。
• 空间复杂度：O(N+E)

[ZacheryCao]

Idea

DFS

Code

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        G = collections.defaultdict(list)
        for f, t in dislikes:
            G[f].append(t)
            G[t].append(f)
        Groups = {}
        def dfs(root, label):
            Groups[root] = label
            for nei in G[root]:
                if nei in Groups and Groups[nei] == label:
                    return False
                elif nei not in Groups and not dfs(nei, -label):
                    return False
            return True

        for i in range(1, n+1):
            if i not in Groups and not dfs(i, 1):
                return False
        return True

Complexity:

Time: O(N +E) Space: O(N +E). O(E) to build relation graph. O(N) to maintain the label of each node

[ZhangNN2018]

class Solution(object):
    def possibleBipartition(self, n, dislikes):
        """
        :type n: int
        :type dislikes: List[List[int]]
        :rtype: bool
        """
        '''
        #BFS
        teams = [0] * (n + 1)
        graph = collections.defaultdict(list)
        for a, b in dislikes:
            graph[a].append(b)
            graph[b].append(a)

        for i in range(1, n+1):
            if teams[i] == 0:
                teams[i] = 1
                Q = collections.deque([i])
                while Q:
                    p = Q.popleft()
                    for neighbor in graph[p]:
                        if teams[neighbor] == teams[p]: return False
                        elif teams[neighbor] == 0:
                            teams[neighbor] = -teams[p]
                            Q.append(neighbor)
        return True

[Alexno1no2]

# 分组信息记录在groups里面
# 0 表示没有分组
# 1 表示分组1
# -1 表示分组2

# 遍历每一个人，尝试给他们进行分组，默认分配组1.
# 然后遍历这个人讨厌的人，尝试给他们分另外一组，如果不可以分配另外一组，则返回False

class Solution:
    def dfs(self, graph, groups, i, group, n):
        groups[i] = group
        for j in range(n):
            if graph[i][j] == 1:
                if groups[j] == group:
                    return False
                if groups[j] == 0 and not self.dfs(graph, groups, j, -1 * group, n):
                    return False
        return True

    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        graph = [[0] * n for i in range(n)]
        groups = [0] * n
        for a, b in dislikes:
            graph[a - 1][b - 1] = 1
            graph[b - 1][a - 1] = 1
        for i in range(n):
            if groups[i] == 0 and not self.dfs(graph, groups, i, 1, n):
                return False
        return True

[LAGRANGIST]

class Solution: def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool: graph = collections.defaultdict(list) for a, b in dislikes: graph[a].append(b) graph[b].append(a)

    colour = {}
    def dfs(node, c=0):
        if node in colour:
            return colour[node] == c
        colour[node] = c

        for neiberhood in graph[node]:
            if not dfs(neiberhood, c ^ 1):
                return False
        return True

    for node in range(1, n+1):
        if node not in colour and not dfs(node):
            return False
    return True

[CodingProgrammer]

思路

图染色法：从一个节点出发，将其染成红色，这个节点不喜欢的节点要染成蓝色，这些蓝色不喜欢的节点又要染成红色，依次类推

代码

class Solution {

    ArrayList<Integer>[] graph;
    int[] colors;

    public boolean possibleBipartition(int n, int[][] dislikes) {
        graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int[] dislike : dislikes) {
            graph[dislike[0]].add(dislike[1]);
            graph[dislike[1]].add(dislike[0]);
        }

        colors = new int[n + 1]; // 1:res -1:blue 0:uncolor

        for (int i = 1; i <= n; i++) {
            if (colors[i] == 0 && !dfs(i, 1)) return false;
        }

        return true;

    }

    // dfs 函数的功能：从 cur 节点出发，将 cur 染成 color 颜色后，继续将 cur 的不喜欢的人染成相反的颜色，看最终是否能够颜色成功
    private boolean dfs(int cur, int color) {
        colors[cur] = color;
        for (int next : graph[cur]) {
            if (colors[next] == color) return false;
            if (colors[next] == 0 && !dfs(next, -color)) return false;
        }
        return true;
    }
}

复杂度

• Time: O(V + N) 其中 V 是 dislikes 的长度
• Space: O(V + N)

[Tesla-1i]

class Solution:
    def dfs(self, graph, colors, i, color, N):
        colors[i] = color
        for j in range(N):
            # dislike eachother
            if graph[i][j] == 1:
                if colors[j] == color:
                    return False
                if colors[j] == 0 and not self.dfs(graph, colors, j, -1 * color, N):
                    return False
        return True

    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = [[0] * N for i in range(N)]
        colors = [0] * N
        for a, b in dislikes:
            graph[a - 1][b - 1] = 1
            graph[b - 1][a - 1] = 1
        for i in range(N):
            if colors[i] == 0 and not self.dfs(graph, colors, i, 1, N):
                return False
        return True

[hdyhdy]

思路： 一个二维数组记录每一个用户的讨厌清单，而color则存储相对应的选择。然后利用深度遍历的方式来对比每个人和他们讨厌的人的喜好是否一致。一致就错了。

func possibleBipartition(n int, dislikes [][]int) bool {
    graph := make([][]int, n+1)
    for _,v := range dislikes {
        graph[v[0]] = append(graph[v[0]], v[1])
        graph[v[1]] = append(graph[v[1]], v[0])
    }

    color := make([]int, n+1) // 两种染色方案，1和-1

    for i := 0;i <= n;i ++ {
        if color[i] != 0 {
            continue
        }

        color[i] = 1 // 新的讨厌圈子第一位染色1就好了
        queue := []int{i}
        for len(queue) != 0 {
            head := queue[0]
            queue = queue[1:]
            for _, v := range graph[head] {
                // 两边都不容，无处容身！
                if color[v] == color[head] {
                    return false
                }
                // 处理过的就无需处理了
                if color[v] != 0 {
                    continue
                }
                queue = append(queue, v)
                if color[v] == 0 {
                    color[v] = -color[head]
                }
            }
        }
    } 
    return true 
}

复杂度都为N+E，E为dislike的大小

[Serena9]

代码

class Solution:
    def dfs(self, graph, colors, i, color, N):
        colors[i] = color
        for j in range(N):
            if graph[i][j] == 1:
                if colors[j] == color:
                    return False
                if colors[j] == 0 and not self.dfs(graph, colors, j, -1 * color, N):
                    return False
        return True

    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = [[0] * N for i in range(N)]
        colors = [0] * N
        for a, b in dislikes:
            graph[a - 1][b - 1] = 1
            graph[b - 1][a - 1] = 1
        for i in range(N):
            if colors[i] == 0 and not self.dfs(graph, colors, i, 1, N):
                return False
        return True

[xuhzyy]

思路

图的遍历+染色法解决问题

代码

class Solution(object):
    def possibleBipartition(self, n, dislikes):
        """
        :type n: int
        :type dislikes: List[List[int]]
        :rtype: bool
        """
        grid = [[0] * n for _ in range(n)]
        colors = [0] * n

        def dfs(i, color):
            colors[i] = color
            for j in range(n):
                if grid[i][j] == 1:
                    if colors[j] == color:
                        return False
                    if colors[j] == 0 and not dfs(j, -1 * color):
                        return False
            return True

        for a,b in dislikes:
            grid[a-1][b-1] = 1
            grid[b-1][a-1] = 1

        for i in range(n):
            if colors[i] == 0 and not dfs(i, 1):
                return False

        return True

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N^2)

[Zhang6260]

JAVA版本

图的二分法

class Solution {
    boolean isFalse = false;
    public boolean possibleBipartition(int n, int[][] dislikes) {
        //构建领接矩阵来存储图的信息
        int arr[][] = new int [n+1][n+1];
        for(int i=0; i< dislikes.length;i++){
            arr[dislikes[i][0]][dislikes[i][1]] = 1;
            arr[dislikes[i][1]][dislikes[i][0]] = 1;
        }
        //dfs来进行访问
        boolean[]colors = new boolean[n+1];
        boolean[]visited = new boolean[n+1];
        for(int i=1;i<=n;i++){
            if(!visited[i])dfs(arr,visited,colors,i);
            if(isFalse)return false;
        }
        return true;
    }
    public void dfs(int[][]arr, boolean[] visited,boolean[]colors,int index){
        visited[index] = true;
        for(int i=1;i<arr.length;i++){
            if(arr[index][i]==0)continue;
            if(!visited[i]){
                colors[i] = !colors[index];
                dfs(arr,visited,colors,i);
            }else if(colors[i]==colors[index]){
                isFalse = true;
            }
        }
    }
}

时间复杂度：O(N + e))

空间复杂度：O(N + e))

[shamworld]

var possibleBipartition = function(n, dislikes) {
     let graph = [...Array(n + 1)].map(() => Array()), // 动态创建二维数组
      colors = Array(n + 1).fill(-1)

    // build the undirected graph
    for (const d of dislikes) {
        graph[d[0]].push(d[1])
        graph[d[1]].push(d[0])
    }

    const dfs = (cur, color = 0) => {
        colors[cur] = color
        for (const nxt of graph[cur]) {
        if (colors[nxt] !== -1 && colors[nxt] === color) return false // conflict
        if (colors[nxt] === -1 && !dfs(nxt, color ^ 1))  return false;
        }
        return true
    };

    for (let i = 0; i < n; ++i)
        if (colors[i] === -1 && !dfs(i, 0)) return false

    return true
};

[xianxianxianyu]

class UnionFound {
public:
    vector<int> F;

    UnionFound(int n)
    {
        F = vector<int>(n, 0);
        for (int i = 0; i < n; i++) {
            F[i] = i;
        }
    }

    int Find(int x)
    {
        if (x == F[x]) {
            return x;
        }
        return F[x] = Find(F[x]);
    }

    void Union(int x, int y)
    {
        x = Find(x);
        y = Find(y);

        if (x != y) {
            F[x] = y;
        }
    }
};

class Solution {
public:
    bool possibleBipartition(int n, vector<vector<int> > &dislikes)
    {
        unordered_map<int, vector<int> > mp;

        for (int i = 0; i < dislikes.size(); i++) {
            mp[dislikes[i][0] - 1].push_back(dislikes[i][1] - 1);
            mp[dislikes[i][1] - 1].push_back(dislikes[i][0] - 1);
        }

        UnionFound uf(n);
        for (int i = 0; i < n; i++) {
            auto vec = mp[i];

            for (auto c : vec) {
                if (uf.Find(i) == uf.Find(c)) {
                    return false;
                }
                uf.Union(vec[0], c);
            }
        }
        return true;
    }
};

[iambigchen]

思路

除了构建图来存储是否喜欢的关系外，还需要colors来存储分组情况。0不是没有分组，1表示分第一组，-1表示第二组。如果当前这个人没有分组，并且它不能分组，则返回false。

是否能分组的条件是：找到当前人的不喜欢人，如果不喜欢的人和当前人分组相同，则不能分组。如果不喜欢的人还没有分组，则为他分为另外一组，继续判断不喜欢的人是否可以分组。

关键点

代码

• 语言支持：JavaScript

JavaScript Code:

/**
 * @param {number} n
 * @param {number[][]} dislikes
 * @return {boolean}
 */
var possibleBipartition = function(n, dislikes) {
    let graph = new Array(n).fill(0).map(() => new Array(n).fill(0))
    let colors = new Array(n).fill(0)
    for (const [a, b] of dislikes) {
        graph[a-1][b-1] = 1
        graph[b-1][a-1] = 1
    }

    for (let i = 0; i < n; i++) {
        if (colors[i] === 0 && !dfs(graph, colors, i, 1, n)) {
            return false
        }
    }
    return true
};

function dfs (graph, colors, i, color, n) {
    colors[i] = color
    for (let j = 0; j < n; j++) {
        if (graph[i][j] == 1) {
            if (colors[j] == color) {
                return false
            } else if (colors[j] == 0 && !dfs(graph, colors, j, -1 * color, n)) {
                return false
            }
        }
    }
    return true
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n**2)$

[wenlong201807]

代码块

/**
 * @param {number[][]} graph
 * @return {boolean}
 */
var isBipartite = function (graph) {
  /* bfs + 染色法 */
  const len = graph.length;
  const colors = new Array(len).fill(0); // 用于存储染色信息的数组，0 表示未染色，1 表示染成红色，2 表示染成绿色

  for (let i = 0; i < len; i++) {
    if (!colors[i]) { // 判断是否被染色，如已染色说明此处已被遍历过了，跳过
      let que = [i]; // 使用队列存储需要被染色的节点下标
      colors[i] = 1; // 初始化第一个的颜色为红色
      while (que.length) { // 通过队列的长度来判断是否结束循环
        const key = que.shift();
        const color = colors[key] === 1 ? 2 : 1; // 记录下该节点的下个节点应该为什么颜色
        for (const item of graph[key]) { // 遍历该节点所有与之相连的节点
          if (colors[item]) { // 如果该节点已被染色，则判断该颜色是否与记录下的颜色一样，不一样则 return false
            if (colors[item] !== color) return false;
          } else { // 如果未被染色，则将其染色，并将其添加进队列中
            colors[item] = color;
            que.push(item);
          }
        }
      }
    }
  }
  return true;
};

时间复杂度和空间复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(1)

[xinhaoyi]

886. 可能的二分法

思路一

用邻接表+dfs

没什么思路，看下题解 这个题目可以转化为：把每个人都看作一个结点，任何两个人互不喜欢就在两个结点间连一条线 全部连好后，形成了一个图，要求只用红蓝两种颜色就能把所有结点都染上色，我们用0代表蓝，1代表红 颜色每次都和和1取异或，即可在0、1间反转 把所有人编号为1 到 N ，（0不要） 我们用一个邻接表存贮图，然后用dfs遍历判断上色情况

代码

class Solution {
    //没什么思路，看下题解
    //这个题目可以转化为：把每个人都看作一个结点，任何两个人互不喜欢就在两个结点间连一条线
    //全部连好后，形成了一个图，要求只用红蓝两种颜色就能把所有结点都染上色，我们用0代表蓝，1代表红
    //颜色每次都和和1取异或，即可在0、1间反转
    //把所有人编号为1 到 N ，（0不要）
    //我们用一个邻接表存贮图
    ArrayList<Integer>[] graph;// 使用邻接表存储图
    Map<Integer,Integer> color;//记录上色结果
    public boolean possibleBipartition(int N, int[][] dislikes) {
        graph=new ArrayList[N+1];// 0位是不用的,我们用1~N位，所以这里是N+1,要注意下
        //ArrayList实例化，即每个结点后连着的一串链给它生成了
        for (int i = 0; i !=N+1; i++) {
            graph[i]=new ArrayList<Integer>();
        }
        //图初始化，注意这个地方因为不会出现重复的数组，即[1,2],[2,1]这种，所以邻接表这样初始化是没有问题的
        //初始化完成后，我们的图也就生成了
        for(int[] cp:dislikes) {
            graph[cp[0]].add(cp[1]);
            graph[cp[1]].add(cp[0]);    
        }
        //用一个哈希表color来表示上色情况，如果key不存在，说明还没上色，否则对应value一定是0或者1
        color=new HashMap();
        for(int node=1;node!=N+1;node++) {
             // 还未上色
            if(!color.containsKey(node)) {
                 //从node开始深度遍历，上色的同时检测有无冲突，即一个红色又要给它涂上蓝色，两个颜色搞不定
                 //先默认蓝色
                boolean ifNoConflict =dfs(node,0);
                 //有冲突
                if(!ifNoConflict) return false; 
            }
             //已经上色，且没有冲突，什么也不用干
        }
        return true;
    }
    private boolean dfs(int node, int c) {
        //从possibleBipartition调用时node是未上色的
        if(color.containsKey(node)) {
             // 若已经上色则看是否上色正确，
            boolean OKColor = color.get(node) == c ? true : false;
            return OKColor;
        }
        color.put(node,c);// 上色
        // 深度遍历
        for(int noFriend:graph[node]) {
            boolean OKColor=dfs(noFriend,c^1);
            if(!OKColor) return false;
        }
        return true;
    }
}

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(n)$

[ZJP1483469269]

class Solution:
    def dfs(self,cur,color,col,dic):
        col[cur] = color
        for i in dic[cur]:
            if col[i] == col[cur]:
                return False
            if col[i]==0 and not self.dfs(i,-1*color,col,dic):
                return False
        return True
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        dic = defaultdict(list)
        col =  [0] * n #记录颜色
        for dis in dislikes:
            dic[dis[0]-1].append(dis[1]-1)#建立邻接表
            dic[dis[1]-1].append(dis[0]-1)
        for i in range(n):
            if not col[i] and not self.dfs(i,1,col,dic):
                return False
        return True

[junbuer]

思路

• 图的遍历 DFS

  对每个人进行染色，如果第一个人是红色，那么他不喜欢的人都是蓝色。任何不喜欢蓝色的人都是红色。

  如果存在冲突则返回false

  class Solution(object):
    def possibleBipartition(self, N, dislikes):
        graph = collections.defaultdict(list)
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)
  
        color = {}
        def dfs(node, c = 0:
            if node in color:
                return color[node] == c
            color[node] = c
            return all(dfs(nei, c ^ 1) for nei in graph[node]) 
  
        return all(dfs(node) for node in range(1, N+1) if node not in color)

  复杂度分析

• 时间复杂度：$O(n + m)$，m为dislikes的长度

• 空间复杂度：$O(n + m)$

[JudyZhou95]

思路

用dfs加上色法，看邻接节点是否都能是不同颜色的。

代码

class Solution: def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
def helper(person_id, color): color_table[person_id] = color

        for p in dislike_table[person_id]:
            if color_table[p] == color:
                return False

            if color_table[p] == 0 and not helper(p, -1 * color):
                return False
        return True

    if n <= 2 or not dislikes:
        return True

    dislike_table = defaultdict(list)
    color_table = defaultdict(int)

    for p1, p2 in dislikes:
        dislike_table[p1].append(p2)
        dislike_table[p2].append(p1)

    for person_id in range(1, n+1):
        if color_table[person_id] == 0 and not helper(person_id, 1):
            return False
    return True

复杂度

TC: O(N) SC: O(N)

[last-Battle]

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        vector<vector<int>> matix(N + 1);

        for (auto& dislike : dislikes) {
            matix[dislike[0]].push_back(dislike[1]);
            matix[dislike[1]].push_back(dislike[0]);
        }

        vector<int> colors(N + 1, 0);
        for (int i = 1; i <= N; ++i) {
            // 已经染色了就跳过
            if (colors[i] != 0) {
                continue;
            }

            colors[i] = 1;

            queue<int> q;
            q.push(i);
            while (!q.empty()) {
                int t = q.front(); q.pop();

                for (auto& cur : matix[t]) {
                    // 和它的dislike元素着色一样，那就分到了一组，就是false
                    if (colors[cur] == colors[t]) {
                        return false;
                    }

                    // 把它的dislike元素着色为相反颜色
                    if (colors[cur] == 0) {
                        colors[cur] = -colors[t];
                        q.push(cur);
                    }
                }
            }
        }

        return true;
    }
};

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[CoreJa]

思路

今天的题被自己菜到了，没看出来是染色问题，光在想怎么去DFS了，没有想到用colors/visited数组/哈希表来表示分组的结果，光在那愣愣的想创建俩集合了。

• DFS：染色问题，深搜最适合解决了
• DFS+all函数：试着用python的all函数简化代码，好用是好用就是慢了不少
• BFS：用辅助空间(队列)处理，在LC上速度比DFS更快

代码

class Solution:
    # DFS: 染色问题，深搜最适合解决了
    def possibleBipartition1(self, n: int, dislikes: List[List[int]]) -> bool:
        graph = defaultdict(list)
        for x, y in dislikes:
            graph[x].append(y)
            graph[y].append(x)
        colors = [-1 for _ in range(n + 1)]

        def dfs(node, color):
            if colors[node] != -1:
                return colors[node] == color
            colors[node] = color
            for other in graph[node]:
                if not dfs(other, 1 ^ color):
                    return False
            return True

        for i in range(1, n + 1):
            if colors[i] == -1:
                if not dfs(i, 0):
                    return False
        return True

    # DFS+all函数：试着用python的all函数简化代码，好用是好用就是慢了不少
    def possibleBipartition2(self, n: int, dislikes: List[List[int]]) -> bool:
        graph = defaultdict(list)
        for x, y in dislikes:
            graph[x].append(y)
            graph[y].append(x)
        colors = [-1 for _ in range(n + 1)]

        def dfs(node, color):
            if colors[node] != -1:
                return colors[node] == color
            colors[node] = color
            return all(dfs(other, 1 ^ color) for other in graph[node])

        return all(dfs(i, 0) for i in range(1, n + 1) if colors[i] == -1)

    # BFS: 用辅助空间(队列)处理，在LC上速度比DFS更快
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        graph = defaultdict(list)
        for x, y in dislikes:
            graph[x].append(y)
            graph[y].append(x)
        colors = [-1] * (n + 1)
        color = 0
        q = deque()
        for i in range(1, n + 1):
            if colors[i] == -1:
                q.append(i)
                while q:
                    node = q.popleft()
                    if colors[node] == -1:
                        colors[node] = color
                    color = colors[node] ^ 1
                    for other in graph[node]:
                        if colors[other] == -1:
                            q.append(other)
                            colors[other] = color
                        elif colors[other] != color:
                            return False
        return True

[tongxw]

思路

相邻顶点尝试用不同颜色染色。

class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        List<Integer>[] graph = new List[n + 1];
        for (int i=1; i<=n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int[] dislike : dislikes) {
            // dislike[0] <-> dislike[1]
            graph[dislike[0]].add(dislike[1]);
            graph[dislike[1]].add(dislike[0]);
        }

        int[] visited = new int[n + 1];
        for (int i=1; i<=n; i++) {
            if (visited[i] == 0) {
                if (!setColor(graph, i, visited, 1)) {
                    return false;
                }
            }
        }

        return true;
    }

    private boolean setColor(List<Integer>[] graph, int people, int[] visited, int color) {
        visited[people] = color;
        for (int neibor : graph[people]) {
            if (visited[neibor] == color) {
                return false;
            } else if (visited[neibor] == 0) {
                setColor(graph, neibor, visited, -color);
            }
        }

        return true;
    }
}

TC: O(V+E) SC: O(V)

[LinnSky]

代码

   var possibleBipartition = function(n, dislikes) {
      let ok = true
      let color = new Array(n + 1).fill(false)
      let visited = new Array(n + 1).fill(false)
      const buildGraph = (n, dislikes) => {
          let graph = new Array(n + 1).fill(0).map(() => new Array())
          for(let edge of dislikes) {
             let v = edge[1]
             let w = edge[0]
            graph[v].push(w)
            graph[w].push(v)
         }
        return graph
      }
      const traverse = (graph, v) => {
          if(!ok) return
          visited[v] = true;
          for(let w of graph[v]) {
             if (!visited[w]) {
                color[w] = !color[v]
                traverse(graph, w)
             } else {
                if (color[w] == color[v]) ok = false
             }
          }
       }

      const graph = buildGraph(n, dislikes);
      for(let i = 0; i <= n; i++) {
         if(!visited[i]) traverse(graph, i)
      }
      return ok
   };

[charlestang]

思路

以 dislike 关系为边，将所有节点建立成图。如果我们可以对一条边的两个节点，进行相异颜色的着色，则满足二分，否则无法二分。 这是一个二分图问题。

代码

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        graph = defaultdict(list)
        for a, b in dislikes:
            graph[a].append(b)
            graph[b].append(a)

        colors = {}
        def dfs(node: int, c: int):
            color = colors.get(node, 0)
            if color == c:
                return True
            elif color == -c:
                return False
            colors[node] = c
            for sibling in graph[node]:
                if not dfs(sibling, -c):
                    return False
            else:
                return True
        for i in range(1, n + 1):
            color = colors.get(i, 0)
            if color == 0 and not dfs(i, 1):
                return False
        else:
            return True

时间复杂度分析 因为深度优先遍历，对每个节点着色一次，时间复杂度 O(n)。

空间复杂度，用了一个邻接节点表，和一个哈希存储着色结果，所以空间复杂度 O(n)

[cszys888]

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        from collections import defaultdict
        graph = defaultdict(list)
        for element in dislikes:
            graph[element[0]].append(element[1])
            graph[element[1]].append(element[0])

        color = {}
        def dfs(node, c = 0):
            if node in color:
                return color[node] == c
            color[node] = c
            return all(dfs(new_node, c ^ 1) for new_node in graph[node])

        return all(dfs(node) for node in range(1,n+1) if node not in color)

time complexity: O(N + E), N is the number of nodes, E is the number of edges space complexity: O(N + E)

[uniqlell]

public boolean possibleBipartition(int N, int[][] dislikes) {
    int[] dp = new int[N+1];
    int k = 1;
    for(int[] dislike : dislikes){
    int a = dislike[0], b = dislike[1];
    if(dp[a] == 0 && dp[b] == 0){//都为初始状态
        dp[a] = k++;
        dp[b] = k++;
    }else if(dp[a] == 0){
        dp[a] = dp[b] % 2 == 0 ? dp[b] - 1 : dp[b] + 1;
    }else if(dp[b] == 0){
        dp[b] = dp[a] % 2 == 0 ? dp[a] - 1 : dp[a] + 1;
    }else{//都不为初始状态
        if(dp[a] == dp[b]) return false;
    }
    }

    return true;
}

[Toms-BigData]

【Day 30】886. 可能的二分法

思路

染色法，无向图，深度优先遍历dfs

golang代码

func possibleBipartition(N int, dislikes [][]int) bool {
    if N == 0 {
        return true
    }
    // 维护每个人讨厌的人物
    graph := make([][]int, N+1)
    for _, v := range dislikes {
        graph[v[0]] = append(graph[v[0]], v[1])
        graph[v[1]] = append(graph[v[1]], v[0])
    }
    color := make([]int, N+1) // 两种染色方案，1和-1
    for i := 1; i <= N; i++ {
        // 如果已经染色了，说明其所在的讨厌圈子已经处理了，不用再看了
        if color[i] != 0 {
            continue
        }
        // 新的讨厌圈子第一位染色1就好了
        if !dfs(i, 1, graph, color) {
            return false
        }
    }
    return true
}

func dfs(node, c int, graph [][]int, color []int) bool {
    // 如果已经染色了，最好和新指派的颜色是一样的
    if color[node] != 0 {
        return color[node] == c
    }
    color[node] = c
    for _, v := range graph[node] {
        if !dfs(v, -c, graph, color) {
            return false
        }
    }
    return true
}

复杂度 时间:O(N+E) 空间:O(N+E)

[Yachen-Guo]

思路

染色法，采用深度优先遍历解决

代码

class Solution {
    ArrayList<Integer>[] graph;
    Map<Integer,Integer> color;

    public boolean possibleBipartition(int n, int[][] dislikes) {
        graph = new ArrayList[n+1];
        for(int i = 0; i != n + 1; i++){
            graph[i] = new ArrayList<Integer>();
        }
        for(int[] cp:dislikes){
            graph[cp[0]].add(cp[1]);
            graph[cp[1]].add(cp[0]);
        }
        color = new HashMap();
        for(int node = 1; node != n+1; node++){
            if(!color.containsKey(node)){
                boolean OK = dfs(node,0);
                if(!OK) return false;
            } else continue;
        }
        return true;
    }

    private boolean dfs(int node, int c){
        if(color.containsKey(node)){
            boolean OK = color.get(node)==c;
            return OK;
        }
        color.put(node,c);
        for(int noFriend:graph[node]){
            boolean OK = dfs(noFriend,c^1);
            if(!OK) return false;
        }
        return true;
    }
}

复杂度分析

时空复杂度 O(N+dislikes的长度)

[didiyang4759]

class Solution(object):
    def possibleBipartition(self, N, dislikes):
        graph = collections.defaultdict(list)
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)

        color = {}
        def dfs(node, c = 0):
            if node in color:
                return color[node] == c
            color[node] = c
            return all(dfs(nei, c ^ 1) for nei in graph[node])

        return all(dfs(node)
                   for node in range(1, N+1)
                   if node not in color)

时间复杂度: O(N+E) 空间复杂度：O(N + E)

[ZZRebas]

思路

先把N个人分为同一组，再遍历数组分为两个组，并标记已经遍历过的n。

代码(Python)

def fun(N,dislikes):
    N_lt=range(1,N+1)
    N_dict=dict.fromkeys(N_lt,0)    #先把N个人分为同一组
    flag_dict=dict.fromkeys(N_lt,0) #对每个人做一个是否遍历过的标记，未遍历设为0，遍历过记为1
    for k,v in dislikes:
        if N_dict[k]==0:
            if flag_dict[k]==1 and flag_dict[v]==1:
                return False
            N_dict[v]=1
            flag_dict[k]=1
            flag_dict[v]=1
        else:
            if N_dict[v]==1:
                return False
            flag_dict[v]=1
    print(N_dict)
    return True

N = 4
dislikes = [[1,2],[1,3],[2,4]]
print(fun(N,dislikes))  #True
N = 4
dislikes = [[1,2],[1,3],[2,3]]
print(fun(N,dislikes))  #False
N = 5
dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
print(fun(N,dislikes))  #False

复杂度分析

• 时间复杂度： O(N)，N为数组长度。
• 空间复杂度：

[chengyufeng6]

class Solution { public: bool possibleBipartition(int n, vector<vector>& dislikes) { vector<vector> g(n+1); for(auto d : dislikes){ g[d[0]].push_back(d[1]); g[d[1]].push_back(d[0]); } vector color(n+1,0); function<bool(int,int)> dfs = [&](int cur_node,int col){ if(color[cur_node]) return color[cur_node] == col; color[cur_node] = col; for(auto next_node : g[cur_node]) if(!dfs(next_node,-col)) return false; return true; }; for(int i = 1; i <= n; i ++){ if(!color[i] && !dfs(i,1)) return false; } return true; } };

[ywang525]

class Solution(object): def possibleBipartition(self, N, dislikes): graph = collections.defaultdict(list) for u, v in dislikes: graph[u].append(v) graph[v].append(u)

    color = {}
    def dfs(node, c = 0):
        if node in color:
            return color[node] == c
        color[node] = c
        return all(dfs(nei, c ^ 1) for nei in graph[node])

    return all(dfs(node)
               for node in range(1, N+1)
               if node not in color)

[alongchong]

class Solution {
    ArrayList<Integer>[] graph;
    Map<Integer, Integer> color;

    public boolean possibleBipartition(int N, int[][] dislikes) {
        graph = new ArrayList[N+1];
        for (int i = 1; i <= N; ++i)
            graph[i] = new ArrayList();

        for (int[] edge: dislikes) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }

        color = new HashMap();
        for (int node = 1; node <= N; ++node)
            if (!color.containsKey(node) && !dfs(node, 0))
                return false;
        return true;
    }

    public boolean dfs(int node, int c) {
        if (color.containsKey(node))
            return color.get(node) == c;
        color.put(node, c);

        for (int nei: graph[node])
            if (!dfs(nei, c ^ 1))
                return false;
        return true;
    }
}

[zol013]

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        '''
        graph = defaultdict(list)
        for a, b in dislikes:
            graph[a].append(b)
            graph[b].append(a)

        colored = {}

        def dfs(node, color):
            if node in colored:
                return colored[node] == color
            colored[node] = color
            for neighbor in graph[node]:
                if not dfs(neighbor, color ^ 1):
                    return False

            return True

        for node in range(1, n + 1):
            if node not in colored:
                if not dfs(node, 0):
                    return False

        return True
        '''

        graph = collections.defaultdict(list)
        for a, b in dislikes:
            graph[a].append(b)
            graph[b].append(a)

        colored = {}

        for i in range(1, n + 1):
            if i not in colored:
                colored[i] = 0
                stack = [i]

                while stack:
                    node = stack.pop()
                    for neighbor in graph[node]:
                        if neighbor not in colored:
                            colored[neighbor] = colored[node] ^ 1
                            stack.append(neighbor)
                        elif colored[neighbor] == colored[node]:
                            return False

        return True