【Day 30 】2022-08-13 - 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

[laofuWF]

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

    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        relation = defaultdict(list)
        # build graph
        for x, y in dislikes:
            relation[x].append(y)
            relation[y].append(x)

        # init color
        coloring = [self.NO_COLOR for i in range(n)]

        for person in range(1, n + 1):
            if coloring[person - 1] == 0 and not self.dfs(relation, coloring, person, self.BLUE):
                return False

        return True

    def dfs(self, relation, coloring, person, color):
        # cannot bipartition
        if coloring[person - 1] != 0:
            if coloring[person - 1] == -color:
                return False
            # prevent infinite loop
            return True

        # paint different color
        if coloring[person - 1] == 0:
            coloring[person - 1] = color

        for enemy in relation[person]:
            if not self.dfs(relation, coloring, enemy, -color):
                return False

        return True        

[xixiao51]

Idea

Graph:

Person <-> Node

P1 and P2 dislike each other <-> Node 1 and Node 2 share one edge, and they can be drawed with different two colors (i.e., for dislike relation)

If we can draw each dislike pair with different two colors, and keep the dislike relationship always, then there exists at least one possible bipartition.

Code

class Solution {
    int[] groups;
    List<List<Integer>> graph;
    public boolean possibleBipartition(int n, int[][] dislikes) {
        // 0: no group, 1 for one group, -1 for another group
        groups = new int[n + 1];
        graph = new ArrayList<List<Integer>>();

        for(int i = 0; i < n + 1; i++) {
            graph.add(new ArrayList<>());
        }

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

        for(int i = 1; i < n + 1; i++) {
            // check all the unvisited node
            if(groups[i] == 0 && !dfs(i, 1)) {
                return false;
            }
        }

        return true;
    }

    private boolean dfs(int i, int group) {
        if(groups[i] != 0) {
            return groups[i] == group;
        }
        groups[i] = group;

        // put dislike node into another group
        for(int j: graph.get(i)) {
            if(!dfs(j, -group)) {
                return false;
            }
        }
        return true;
    }
}

Complexity Analysis

• Time complexity: O(V + E)
• Space complexity: O(V ^ 2)

[djd28176]

class Solution {
    List<List<Integer>> graph;
    Map<Integer,Integer> color;
    public boolean possibleBipartition(int n, int[][] dislikes) {
        graph = new ArrayList<>();
        color = new HashMap<>();

        for(int i = 1; i <= n; i++){
            graph.add(new ArrayList<>());
        }
        for(int[] edge: dislikes){
            graph.get(edge[0]-1).add(edge[1]-1);
            graph.get(edge[1]-1).add(edge[0]-1);
        }

        for(int node = 0; node < n; ++node){
            if(!color.containsKey(node) && !dfs(node, 1)){
                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.get(node)){
            if(!dfs(nei, -c)){
                return false;
            }
        }
        return true;
    }
}

[MichaelXi3]

Idea

二部图判定

Code

/**************************
本题考查：Graph + DFS
要点：二部图的判定 + 染色法
**************************/

class Solution { public boolean possibleBipartition (int n, int[][] dislikes) { // 历遍并录入 Graph 中的所有 edges！ // edge 在此题表示的是两个人相互讨厌，所以edge两端应染成不同的颜色 int[][] graph = new int[n+1][n+1]; for (int[] d : dislikes) { graph[d[0]][d[1]] = 1; graph[d[1]][d[0]] = 1; }

    // 下面是“邻接矩阵”，相当于是画板，需要我们去给Graph涂色
    // 利用DFS涂色，若出现颜色conflict则二部图不存在
    int[] group = new int[n+1];
    for (int i=1; i < n+1; i++) {
        // 若该节点还没被上色，则进行DFS染色
        if (group[i] == 0 && !dfs(graph, group, i, 1)) {
            return false;
        }
    }
    // 若所有branch都DFS染色完毕之后依然没有遇到conflicts，则该图为二部图
    return true;
}

private boolean dfs (int[][] graph, int[] group, int index, int grpNum) {
    // 给当前节点染色
    group[index] = grpNum;
    // 历遍和这个节点连接的所有节点（与该节点有dislike关系的全部节点）
    for (int i=1; i < graph.length; i++) {
        // 如果毗邻的节点与自己颜色相同，则出现了两个互相dislike的人在一起的情况，冲突
        if (graph[index][i] == 1 && group[i] == grpNum) {
            return false;
        }
        // 如果毗邻的节点还没有染色，则继续recursive_DFS染色
        if (graph[index][i] == 1 && group[i] == 0 && !dfs(graph, group, i, -grpNum)) {
            return false;
        }
    }
    // 在DFS染色完以这个index为起始点的branch时，若始终没有遇到conflict，则return true
    return true;
}

}

[yopming]

// 二分图题目。可用DFS，可用BFS。下面答案是BFS方法。
// 先把dislikes构造成一个graph，然后尝试给所有的node分配颜色，如果所有的点与其相邻的点（不喜欢的点）颜色不同，则可分成两组

// Time: O(V+E)
// Space: O(V+E)
class Solution {
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
      std::vector<std::vector<int>> g(n); // build the graph matrix
      for (const auto& dislike: dislikes) {
        g[dislike[0] - 1].push_back(dislike[1] - 1);
        g[dislike[1] - 1].push_back(dislike[0] - 1);
      }
      
      std::queue<int> q; // queue for bfs
      std::vector<int> colors(n, 0); // coloring, 0 for ungrouped, 1 and -1 for two groups
      for (int i = 0; i < n; i++) {
        if (colors[i] != 0) continue; // already colored
        q.push(i);
        colors[i] = 1; // assign one color
        while (!q.empty()) {
          int curr = q.front();
          q.pop();
          // traverse all adj nodes of curr
          for (int adj: g[curr]) {
            // case 1, two nodes which dislike each other are assigned to one group
            if (colors[adj] == colors[curr]) {
              return false;
            }
            
            // case 2, adj colored, but different value
            if (colors[adj] != 0) {
              continue;
            }
            
            colors[adj] = -colors[curr]; // assign the other color
            q.push(adj);
          }
        }
      }
      
      return true;
    }
};

[dereklisdr]

思路：二分图

class Solution {

private boolean ok = true;
private boolean[] color;
private boolean[] visited;

public boolean possibleBipartition(int n, int[][] dislikes) {
    color = new boolean[n + 1];
    visited = new boolean[n + 1];
    List<Integer>[] graph = buildGraph(n, dislikes);

    for (int v = 1; v <= n; v++) {
        if (!visited[v]) {
            traverse(graph, v);
        }
    }
    return ok;
}

private List<Integer>[] buildGraph(int n, int[][] dislikes) {
    List<Integer>[] graph = new LinkedList[n + 1];
    for (int i = 1; i <= n; i++) {
        graph[i] = new LinkedList<>();
    }
    for (int[] edge : dislikes) {
        int v = edge[1];
        int w = edge[0];
        // v -> w
        graph[v].add(w);
        // w -> v
        graph[w].add(v);
    }
    return graph;
}

private void traverse(List<Integer>[] graph, int v) {
    if (!ok) return;
    visited[v] = true;
    for (int w : graph[v]) {
        if (!visited[w]) {
            color[w] = !color[v];
            traverse(graph, w);
        } else {
            if (color[w] == color[v]) {
                ok = false;
            }
        }
    }
}

}

[thinkfurther]

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        if n == 1 or not dislikes:
            return True
        self.n = n
        self.graph = [[False for i in range(n)] for j in range(n)]
        self.colors = [0 for i in range(n)]

        for person1, person2 in dislikes:
            self.graph[person1 - 1][person2 - 1] = True
            self.graph[person2 - 1][person1 - 1] = True

        for i in range(n):
            if self.colors[i] == 0 and not self.dfs(i, 1): # color as 1 for the first cell
                return False

        return True

    def dfs(self, i, color):
        self.colors[i] = color

        for j in range(self.n):
            if self.graph[i][j] == False:
                continue

            if self.colors[j] == color:
                return False

            if self.colors[j] == 0 and not self.dfs(j, -color):
                return False
        return True

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

[aiweng1981]

思路

• 思路描述:这块内容很陌生，先抄答案吧

代码

#代码
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+E)

[Cusanity]

Solution

Language: Java

class Solution {
    private boolean ok = true;
    private boolean[] color;
    private boolean[] visited;
    public boolean possibleBipartition(int n, int[][] dislikes) {
        color = new boolean[n + 1];
        visited = new boolean[n + 1];
        List<Integer>[] graph = buildGraph(n, dislikes);
        for (int v = 1; v <= n; v++) {
            if (!visited[v]) {
                traverse(graph, v);
            }
        }
        return ok;
    }
    private List<Integer>[] buildGraph(int n, int[][] dislikes) {
        List<Integer>[] graph = new LinkedList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new LinkedList<>();
        }
        for (int[] edge : dislikes) {
            int v = edge[1];
            int w = edge[0];
            graph[v].add(w);
            graph[w].add(v);
        }
        return graph;
    }
    private void traverse(List<Integer>[] graph, int v) {
        if (!ok) return;
        visited[v] = true;
        for (int w : graph[v]) {
            if (!visited[w]) {
                color[w] = !color[v];
                traverse(graph, w);
            } else {
                if (color[w] == color[v]) {
                    ok = false;
                }
            }
        }
    }
}

[2learnsomething]

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)

[mo-xiaoxiu]

思路

• dfs
  • 构建无向图：构建无向图的原因是一个子数组[ai, bi]表示的是ai不喜欢bi，那么ai和bi不可能在同一个组，所以也可以理解成bi不喜欢ai，所以是双向的
  • 对两组互不喜欢的人表示不同的颜色，比如红色和蓝色，对构建的无向图进行染色
  • dfs：遍历不同编号的人，一开始默认初始化染为红色（1），对它进行深度优先搜索，对该节点的邻居进行判断
    • 如果邻居没有染色，则需要将邻居染成与当前节点相反的颜色
    • 如果邻居已经染色，则判断与当前节点是否一致，如果一致则冲突返回false，如果是不同的颜色，则以该邻居继续深度优先搜素（递归）

pic

具体实现

class Solution {
public:
    int color[2001] = {0};

    bool dfs(vector<vector<int>>& edges, int index, int c) {
        for(auto& n: edges[index]) {
            if(color[n] == c) return false; //颜色一致，冲突
            if(color[n] == 0) {
                color[n] = c == 1 ? 2 : 1;
                dfs(edges, n, color[n]);
            }
        }

        return true;
    }

    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        vector<vector<int>> edges(n + 1); //初始化：无颜色
        for(auto& d: dislikes) { //初始化无向图
            edges[d[0]].emplace_back(d[1]);
            edges[d[1]].emplace_back(d[0]);
        }

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

        return true;
    }
};

[flaming-cl]

// 此题先建图
// d[0] 和 d[1] 不对付
// 那么 d[1] 肯定也和 d[0] 不对付了

// 我们建上一个没头脑和不高兴的图
// [[1,2], [1, 3], [2, 4]]

// 建图：
// [null, [2,3], [1, 4], [1], [2]]

// BFS 遍历：
// 来一个小朋友，如果他身上没标签，就给他们打上不高兴小标签
// 不高兴小朋友入队列
// 遍历不高兴讨厌的人：
// - 未被标记过，根据邻居是否是不高兴来给他标记，入队列
// - 被标记过，还被标记了不高兴（不高兴只讨厌没头脑啊，不会讨厌不高兴，非黑即白的分组方法失败

// T & S: O(N+ dislikes.length)
class Solution {
    public boolean possibleBipartition(int N, int[][] dislikes) {
        int[] cache = new int[N + 1];
        List<List<Integer>> unhappyAndBrainless = new ArrayList<>(N + 1);
        for(int i = 0; i <= N; i++) unhappyAndBrainless.add(new ArrayList<Integer>());
        for(int[] d : dislikes) {
            unhappyAndBrainless.get(d[0]).add(d[1]);
            unhappyAndBrainless.get(d[1]).add(d[0]);
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            if (cache[i] == 0) {
                cache[i] = 1;
                q.add(i);
                while (!q.isEmpty()) {
                    int unhappy = q.poll();
                    for (int brainless : unhappyAndBrainless.get(unhappy)) {
                        if (cache[brainless] == cache[unhappy]) {
                            return false;
                        }
                        if (cache[brainless] == 0) {
                            cache[brainless] = cache[unhappy] + 1;
                            q.add(brainless);
                        }
                    }
                }
            }
        }
        return true;
    }
}

[lsunxh]

Red and Black Coloring

bfs all components in the graph, assigning each node red/black and its neighbors(haters) opposite colors.

If we encounter a conflict, return false immediately

class Solution(object):
    def possibleBipartition(self, n, dislikes):
        """
        :type n: int
        :type dislikes: List[List[int]]
        :rtype: bool
        """
        g1 = set()
        g2 = set()
        seen = set()
        haters = [[] for i in range(n+1)]
        for a, b in dislikes:
            haters[a].append(b)
            haters[b].append(a)
        for i in range(1, n+1):
            if i not in seen:
                curNodes = [i]
                nextNodes = []
                # bfs on i
                g1.add(i)
                red = True
                while curNodes:
                    cur = curNodes.pop()
                    for hater in haters[cur]:
                        if hater not in seen:
                            nextNodes.append(hater)
                            seen.add(hater)
                        if red:
                            if hater in g1:
                                return False
                            g2.add(hater)
                        else:
                            if hater in g2:
                                return False
                            g1.add(hater)
                    if curNodes == []:
                        curNodes = nextNodes
                        nextNodes = []
                        red = not red
        return True

Time: O(V+E), Space: O(V*E)

[xi2And33]

const possibleBipartition = (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;
};

[testplm]

import collections

class Solution(object):
    def possibleBipartition(self, n, dislikes):
        Not_COLORED,BLUE,GREEN = 0,1,-1
        def helper(person_id,color):
            color_table[person_id] = color
            for the_other in dislike_table[person_id]:
                if color_table[the_other] == color:
                    return False
                if color_table[the_other] == Not_COLORED and not helper(the_other,-color):
                    return False
            return True
        if n==1 or not dislikes:
            return True
        dislike_table = collections.defaultdict(list)
        color_table = collections.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] == Not_COLORED and not helper(person_id,BLUE):
                return False
        return True

[wzasd]

代码

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;
    }

[haoyangxie]

Idea

BFS or DFS

code

// BFS
class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n+1; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] dis : dislikes) {
            graph.get(dis[0]).add(dis[1]);
            graph.get(dis[1]).add(dis[0]);
        }

        int[] colors = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            if (colors[i] == 0) {
                Queue<Integer> queue = new LinkedList<>();
                queue.add(i);
                colors[i] = 1;
                while (!queue.isEmpty()) {
                    int rm = queue.poll();
                    for (int node : graph.get(rm)) {
                        if (colors[node] == 0) {
                            colors[node] = -colors[rm];
                            queue.add(node);
                        } else if (colors[node] == colors[rm]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}

// DFS
class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        List<Integer>[] adj = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : dislikes) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }
        int[] colors = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            if (colors[i] == 0) {
                if (!dfs(i, adj, colors, 1)) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean dfs(int node, List<Integer>[] adj, int[] colors, int color) {
        if (colors[node] != 0) {
            return colors[node] == color;
        }
        colors[node] = color;
        for (int neighbour : adj[node]) {
            if (!dfs(neighbour, adj, colors, -color)) {
                return false;
            }
        }
        return true;
    }
}

complexity

Time: O(V+E) Space: O(V+E)

[Yueza]

思路

建图+染色

代码

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

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

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

复杂度

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

[herbertpan]

code

class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        Map<Integer, Set<Integer>> peopleToDislikes = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            peopleToDislikes.put(i, new HashSet<>());
        }
        for (int[] dislike : dislikes) {
            peopleToDislikes.get(dislike[0]).add(dislike[1]);
            peopleToDislikes.get(dislike[1]).add(dislike[0]);
        }

        Map<Integer, Integer> peopleToColor = new HashMap<>();
        boolean[] explored = new boolean[n + 1];
        // Use BFS to group different people
        for (Map.Entry<Integer, Set<Integer>> entry : peopleToDislikes.entrySet()) {
            int people = entry.getKey();
            if (peopleToColor.containsKey(people)) {  // if we have visted this people in previous graph traversal 
                continue;
            }

            int peopleColor = 1;                      // let place this person in group 1 
            peopleToColor.put(people, peopleColor);
            explored[people] = true;

            // Set<Integer> disliked = entry.getValue();
            Queue<Integer> dislikeQ = new LinkedList<>();
            dislikeQ.addAll(entry.getValue());

            while (!dislikeQ.isEmpty()) {
                peopleColor = peopleColor * -1;
                int size = dislikeQ.size();
                for (int i = 0; i < size; i++) {
                    people = dislikeQ.poll();

                    if (peopleToColor.containsKey(people) && peopleToColor.get(people) != peopleColor) {
                        return false;
                    } else {
                        peopleToColor.put(people, peopleColor);
                    }

                    if (explored[people]) { continue; }
                    explored[people] = true;
                    dislikeQ.addAll(peopleToDislikes.get(people));
                }
            }
        }
        return true;
    }
}

Complexity

1. Time: O(n^2)
2. Space: O(n + E)

[lzyxts]

Idea

• 遍历dislikes生成关系图，记录每一个人对应的不能成为同一组的其他人
• 假设第一个人在A组，那么讨厌的人将会在B组，B组讨厌的人会放在A组。对于当事人i来说，判断i讨厌的人是否出现过；如果出现，又和i在同一组，则返回false。如果没有出现过则放入对方组，检查下一个人。

Code

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        if not dislikes:
            return True
        group = defaultdict(int)
        store = defaultdict(list)

        for rls in dislikes:
            store[rls[0]].append(rls[1])
            store[rls[1]].append(rls[0])

        people = set(store.keys())
        seen = set()

        for person in people:

            if person not in seen:
                seen.add(person)
                group[person] = 1
                cur = [person]

                while cur:
                    p1 = cur.pop()
                    for p2 in store[p1]:
                        if p2 not in seen:
                            seen.add(p2)
                            cur.append(p2)
                            group[p2] = group[p1]*-1

                        if p2 in seen and group[p2] == group[p1]:
                            return False

        return True

Complexity

• Time：O(e+v)
• Space：O(e+v)

[Whisht]

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        from collections import defaultdict
        graph = defaultdict(list)
        for a,b in dislikes:
            graph[a-1].append(b-1)
            graph[b-1].append(a-1)
        colors = [0]*n
        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 graph[i]:
            if colors[j] == color:
                return False
            if colors[j] == 0 and not self.dfs(graph,colors,j,-1*color,n):
                return False
        return True

[zch-bit]

Day 30

func possibleBipartition(n int, dislikes [][]int) bool {
    color := make([]int, n+1)
    for i := 1; i <= n; i++ {
        color[i] = -1
    }

    m := map[int][]int{}
    for _, dislike := range dislikes {
        a, b := dislike[0], dislike[1]
        m[a] = append(m[a], b)
        m[b] = append(m[b], a)
    }
    var dfs func(int, int) bool
    dfs = func(node int, c int) bool {
        if color[node] != -1 {
            return color[node] == c
        }
        color[node] = c
        for _, nextNode := range m[node] {
            if !dfs(nextNode, 1-c) {
                return false
            }
        }

     return true
    }

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

    return true
}

[passengersa]

class Solution {

int[] val;
boolean flag;
List<List<Integer>> list=new ArrayList<>();

public boolean possibleBipartition(int N, int[][] dislikes) {

    flag=false;
    val=new int[N+1];

    for(int i=0;i<=N;i++)
        list.add(new ArrayList<>());

    for(int i=0;i<dislikes.length;i++) {
        int x=dislikes[i][0];
        int y=dislikes[i][1];
        list.get(x).add(y);
        list.get(y).add(x);
    }

    for(int i=1;i<=N;i++)
        val[i]=-1;

    for(int i=1;i<=N;i++) {
        if(val[i]!=-1)
            continue;
        dfs(i,-1,0);
    }

    return !flag;
}

private void dfs(int u,int p,int step) {

    if(val[u]!=-1) {
        if((step-val[u])%2!=0)
            flag=true;
        return;
    }

    val[u]=step;

    if(flag) return;

    for(int i=0;i<list.get(u).size();i++) {
        int v=list.get(u).get(i);
        if(v==p) continue;
        dfs(v,u,step+1);
    }
}

}

[ceramickitten]

思路

二分图+染色

代码

from collections import defaultdict
from typing import List

RED, BLUE = True, False

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

        colors = {}

        def dfs(people, color):
            if people in colors:
                return colors[people] == color
            colors[people] = color
            return all(dfs(dislike_people, not color) for dislike_people in dislike_peoples[people])

        return all(dfs(people, RED) for people in range(1, n + 1) if people not in colors)

复杂度分析

e = dislikes.length

• Time: O(n + e)
• Space: O(n + e)

[youzhaing]

题目：886. 可能的二分法

思路

dfs+图+双色填充。选中一个没染色的点，然后给点涂红色，则它的所有邻居应该涂蓝色，但如果此时其中一个邻居是红色，则说明有冲突，返回False。

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)

        color = dict()
        def dfs(node, c):
            # 此node应该赋予颜色c
            if node in color:
                return color[node] == c
            color[node] = c
            # 颜色只有0，1两种取值，所以用1-c代表另一种颜色
            # node的所有邻居都应该赋予颜色1-c
            return all(dfs(neighbor, 1-c) for neighbor in graph[node])
        # 对于没有颜色的点赋予颜色0，若有颜色则说明该点是之前某点的邻居并且成功通过测试，
        # 则不需要对该点重新赋予颜色0
        return all(dfs(node, 0) for node in range(1, n+1) if node not in color)

复杂度

• 时间复杂度：O(n+k), k = len(dislikes), 创建图复杂度是O(k), 遍历判断是O(n)
• 空间复杂度：O(n+k)

[shellyLCooper]

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;
    }
}

[LiquanLuo]

/***
Solution:
(1) construct adjacent list, for dislike[a,b], create two relationships, a :... b , b:... a Time: O(n) Space: O(n)
(2) construct color vector: [0,....,0] n + 1  SO(n)
(3) push the all the elements into the stack  TO(n)
(4) pop node from stack, if it has not been colored, color 1,  TO(n)
    and try to color all its adjacent node to -1, if conflicts, return false
(5) if no conflicts, return true

Time: O(V + E)
Space: O(V + E)

***/

class Solution {
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        if (dislikes.size() == 0) {
            return true;
        }
        unordered_map<int, vector<int>> adj;
        // since the number of people is fixed, n
        // we do not have to use hash map
        // we can simplify to vector<vector<int>>
        for (auto dislike : dislikes) {
            if (adj.find(dislike[0]) != adj.end()) {
                adj[dislike[0]].push_back(dislike[1]);
            }
            else {
                vector<int> v{dislike[1]};
                adj[dislike[0]] = v;
            }

            if (adj.find(dislike[1]) != adj.end()) {
                adj[dislike[1]].push_back(dislike[0]);
            }
            else {
                vector<int> v{dislike[0]};
                adj[dislike[1]] = v;
            }

        }

        unordered_set<int> visited;
        stack<int> s;
        for (int i = n; i >= 1; --i) {
            s.push(i);
        }

        vector<int> colors(n + 1, 0);
        s.push(dislikes[0][0]);
        while (!s.empty()) {
            auto node = s.top();
            // cout << "node: " << node << endl;
            s.pop();
            if (visited.find(node) != visited.end()) {
                continue;
            }
            else {
                visited.insert(node);
            }

            int color = 1;
            if (colors[node] != 0) {
                color = colors[node];
            }
            else {
                colors[node] = 1;
            }

            if (adj.find(node) != adj.end()) {
                for (auto neighbor : adj[node]) {

                    if (colors[neighbor] == 0) {
                        colors[neighbor] = -color;
                        s.push(neighbor);
                    }
                    else {
                        if (colors[neighbor] != -color) {
                            return false;
                        }
                    }
                    // cout << "neighbour " << neighbor << " color: " <<colors[neighbor] << endl;
                }
            } 
        }
        // cout << "ddddd" << endl;
        return true;      
    }
};

[Tlntin]

题目链接

-链接

代码

class Solution {
public:
  bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
    // 记录每个元素的位置，左边组还是右边组, 左边组标记为-1， 右边组标记为1
    // 如果一个元素出现同时为1又为2，则return False
    // 否则返回True
    // 记录每个节点的邻居节点
    std::unordered_map<int, std::vector<int>> graph;
    for (const auto & data: dislikes) {
      graph[data[0]].push_back(data[1]);
      graph[data[1]].push_back(data[0]);
    }
    // 记录每个节点的颜色，或者说组别，颜色为1或者-1,如果为0则未初始化 
    std::vector<int> color(n + 1, 0);
    for (const auto & item: graph) {
      // 没染过色的默认按-1给染色
      if (color[item.first] == 0) {
        if(dfs(item.first, -1, graph, color) == false) {
          return false;
        }
      }
    }
    return true;
  }
  bool dfs(
    int x, int c, 
    std::unordered_map<int, std::vector<int>> & graph, 
    std::vector<int> & color
  ) {
    // 先判断当前节点是否有分组
    // 如果已经分组，需要打断它，防止无限循环(非常重要)
    if (color[x] != 0) {
      return color[x] == c;
    }
    color[x] = c;
    // 遍历x节点的邻居节点，让x的邻居节点全部分组值为-c
    for (const int & i: graph[x]) {
      // 对邻居节点进行同样操作，并且判断其返回是否为false,如果是false则返回false
      if (dfs(i, -c, graph, color) == false) {
        return false;
      }
    }
    // 遍历了所有邻居都没有问题，那就返回true
    return true;
  }
};

int main() {
  std::vector<std::vector<int> > v1({{1, 2}, {1, 3}, {2, 4}});
  Solution s;
  std::cout << s.possibleBipartition(4, v1) << std::endl;
}

复杂度

• 时间：O(n)
• 空间：O(n)

结果

[yingchehu]

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        graph = [[0] * n for i in range(n)]
        for edge in dislikes:
            print(edge)
            graph[edge[0]-1][edge[1]-1] = 1
            graph[edge[1]-1][edge[0]-1] = 1

        colors = [0] * n

        # 確保所有的節點都上色了，從還沒上色的節點開始 dfs 下去塗色
        for i in range(n):
            if colors[i] == 0:
                if not self.dfs(graph, colors, n, i, 1):
                    # 一旦塗色失敗就回錯
                    return False
        return True

    def dfs(self, graph, colors, n, i, color):
        colors[i] = color
        for j in range(n):
            # 如果 i 與 j 相連
            if graph[i][j] == 1:
                # 如果 j 已經上過色，而且還跟 i 同樣顏色，就回傳塗色失敗
                if colors[j] == color:
                    return False
                # 如果 j 還沒上過色，就繼續 dfs 塗色
                if colors[j] == 0:
                    # 一旦有塗色失敗，就直接回傳失敗
                    if not self.dfs(graph, colors, n, j, -1 * color):
                        return False
        return True

複雜度

• Time: O(V+E)
• Space: O(V^2)

[ashleyyma6]

Idea

• BFS
• A dictionary to put person and a list of people dislikes
• Traverse 2D array dislikes to fill the dictionary, create a relationship enrty for everyone
• A queue to save person that have not check yet
• A color array contains: 1, -1 to mark people in different group. A dislikes B, A must have different mark with B
• Traverse the dictionary, mark person different color, add the unchecked person into a queue. If meet mark confict, return false. If all checked, return true.
• https://www.youtube.com/watch?v=0ACfAqs8mm0

Code

    public boolean possibleBipartition(int n, int[][] dislikes) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for(int[] disklike:dislikes){
            List<Integer> curr_list;
            if(graph.containsKey(disklike[0])){
                curr_list = graph.get(disklike[0]);
            }else{
                curr_list = new ArrayList<>();
            }
            curr_list.add(disklike[1]);
            graph.put(disklike[0],curr_list);
            if(graph.containsKey(disklike[1])){
                curr_list = graph.get(disklike[1]);
            }else{
                curr_list = new ArrayList<>();
            }
            curr_list.add(disklike[0]);
            graph.put(disklike[1],curr_list);
        }
        Queue<Integer> queue = new LinkedList<>();
        int[] colors = new int[n+1];
        for(int i = 0;i<n;i++){
            if(colors[i]==0){
                colors[i] = 1;
                queue.add(i);
                while(!queue.isEmpty()){
                    int curr = queue.poll();
                    List<Integer> curr_list = graph.get(curr);
                    if(curr_list!=null){
                        for(Integer check:curr_list){
                            if(colors[curr]==colors[check]){
                                return false;
                            }
                            if(colors[check]==0){
                                colors[check] = -colors[curr];
                                queue.add(check);
                            }
                        }
                    }
                }
            }
        }
        return true;

    }

Complexity Analysis

• Time Complexity:O(e+n) // e = pairs in dislikes
• Space Complexity: O(e+n)

[hydelovegood]

思路

建图，两个部分之间不能有重合矛盾点

代码

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        g=collections.defaultdict(list)
        for i,j in dislikes:
            g[i].append(j)
            g[j].append(i)
        dic={}
        def dfs(node,c=0):
            if node in dic:
                return dic[node]==c
            dic[node]=c
            for nxt in g[node]:
                if not dfs(nxt,c^1):
                    return False
            return True

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

复杂度

时间复杂度On 空间复杂度On

[Mryao1]

解题思路

通过图的入度和出度来解题，根据题意，a信任b，则a的出度增加1，b的入度增加1。这样只有当一个人满足出度为0（不信任任何人），入度为n-1（除法官都信任法官）的时候，这个人就是法官。

代码

public class Q997FindTheTownJudge {

    public int findJudge(int n, int[][] trust) {

        int[] inEdges = new int[n+1];
        int[] outEdges = new int[n+1];
        for (int[] ints : trust) {
            outEdges[ints[0]]++;
            inEdges[ints[1]]++;
        }

        for (int i = 1; i < n+1; i++) {
            if (inEdges[i] == n-1 && outEdges[i] == 0){
                return i;
            }
        }
        return -1;
    }
}

测试

public class Q997FindTheTownJudgeTest {

    private Q997FindTheTownJudge q = new Q997FindTheTownJudge();

    @Test
    public void test1() {
        assertEquals(2, q.findJudge(2, new int[][]{{1,2}}));
    }

    @Test
    public void test2() {
        assertEquals(3, q.findJudge(3, new int[][]{{1,3},{2,3}}));
    }

    @Test
    public void test3() {
        assertEquals(-1, q.findJudge(3, new int[][]{{1,3},{2,3},{3,1}}));
    }
}

[luckyoneday]

代码 js

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

  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; 
      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;
};

[Mryao1]

解题思路

着色法，假设第一组的人是红色，第二组的人是蓝色，有以下推论，一个人是红色的，那他不喜欢的人就都是蓝色的，即所有不喜欢红色的人都是蓝色的，所有不喜欢蓝色的人都是红色的。 如果在着色的过程中有冲突那就是false，没有冲突，所有人着色完毕，那就是true。 从任一个人开始，先给他着红色，然后把他所有不喜欢的人着蓝色，在把不喜欢人的不喜欢的人再着红色，即深度优先遍历，每次着色前判断是否已经着色和所着颜色是否正确即可。

代码

public class Q886PossibleBipartition {

    ArrayList<Integer>[] adjList;
    Map<Integer, Integer> colorMap;

    public boolean possibleBipartition(int n, int[][] dislikes) {
        adjList = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            adjList[i] = new ArrayList<>();     //初始化邻接表
        }
        for (int[] dislike : dislikes) {
            adjList[dislike[0]].add(dislike[1]);        //填充邻接表
            adjList[dislike[1]].add(dislike[0]);
        }

        colorMap = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            if (!colorMap.containsKey(i) && !dfs(i, 0)){    
                //如果该点未着色，则进行着色
                return false;
            }
        }
        return true;
    }

    private boolean dfs(int i, int n) {
        if (colorMap.containsKey(i)){
            return colorMap.get(i) == n;    //如果该点所着颜色不和，则返回false
        }
        colorMap.put(i, n);
        for (Integer j : adjList[i]) {
            if (!dfs(j, n ^ 1)){
                return false;
            }
        }
        return true;
    }
}

[wsmmxmm]

内啥 图还没学明白，等着学好补一下

[eden-ye]

思路

二分染色。 长度n * n的二维boolean数组来存储相互厌恶关系，长度n的数组存储分组情况。 遍历每一个i进行dfs，检查他的相互厌恶情况，如果有人讨厌i，就要和i分在不同组，并且以他为主角进行下一轮的dfs。一旦发现无法给厌恶主角的人分组（已在同一组或者拿到他的dfs false），就立即返回false。

代码

class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        boolean[][] dis = new boolean[n + 1][n + 1];
        for (int[] dislike : dislikes) {
            dis[dislike[0]][dislike[1]] = true;
            dis[dislike[1]][dislike[0]] = true;
        }
        int[] group = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            if (group[i] == 0 && !dfs(dis, i, group, 1, n)) {
                return false;
            }
        }
        return true;

    }
    public boolean dfs(boolean[][] dislike, int index, int[] group, int groupName, int n) {
        group[index] = groupName;
        for (int i = 1; i < n + 1; i++) {
            if (i == index) continue;
            if (dislike[index][i]) {
                if (group[i] == groupName) return false;
                if (group[i] == 0 && !dfs(dislike, i, group, groupName * -1, n)) {
                    return false;
                }
            }
        }
        return true;
    }
}

复杂度

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

[shiyishuoshuo]

code

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        # corner case
        if n == 1 or not dislikes:
            return True
        NOT_COLORED, BLUE, GREEN = 0, 1, -1

        def helper(person_id: int, color: int) -> bool:
            color_table[person_id] = color

            for other in dislike_table[person_id]:
                if color_table[other] == color:
                    return False
                if color_table[other] == NOT_COLORED and (not helper(other, -color)):
                    return False
            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):
            if color_table[person_id] == NOT_COLORED and (not helper(person_id, BLUE)):
                return False

        return True

[nikojxie]

var possibleBipartition = function(n, dislikes) {
  let graph = [...Array(n + 1)].map(() => Array())
  let colors = Array(n + 1).fill(-1)

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

  function dfs(cur, color = 0) {
    colors[cur] = color
    for (const nxt of graph[cur]) {
      if (colors[nxt] !== -1 && colors[nxt] === color) return false
      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
};

[luhaoling]

Idea

使用二分图，先构造好邻接矩阵，然后使用dfs算法遍历，来判断这个图是不是二分图。

Code

class Solution {
    private boolean ok=true;
    private boolean[] color;
    private boolean[] visited;

    public boolean possibleBipartition(int n,int[][] dislikes){
       color=new boolean[n+1];
       visited=new boolean[n+1];

       List<Integer>[] graph=buildGraph(n,dislikes);

       for(int v=1;v<=n;v++){
           if(!visited[v]){
               traverse(graph,v);
           }
       }
       return ok;
    }

    private List<Integer>[] buildGraph(int n,int[][] dislikes){
        List<Integer>[] graph=new LinkedList[n+1];
        for(int i=0;i<=n;i++){
            graph[i]=new LinkedList<>();
        }
        for(int[] edge:dislikes){
            int v=edge[1];
            int w=edge[0];
            graph[v].add(w);
            graph[w].add(v);
        }
        return graph;
    }
    private void traverse(List<Integer>[] graph,int v) {
        if (!ok) return;
        visited[v] = true;
        for (int w : graph[v]) {
            if (!visited[w]) {
                color[w] = !color[v];
                traverse(graph, w);
            } else {
                if (color[w] == color[v]) {
                    ok = false;
                }
            }
        }
    }
}

[zzzkaiNS]

思路

染色法

代码

class Solution {
public:
    vector<vector<int>> g;
    vector<int> color;

    bool dfs(int u, int c) {
        color[u] = c;
        for (int v: g[u])
            if (color[v]) {
                if (color[v] == c) return false;
            } else if (!dfs(v, 3 - c)) {
                return false;
            }
        return true;
    }

    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        g.resize(n);
        color.resize(n);
        for (auto& e: dislikes) {
            int a = e[0] - 1, b = e[1] - 1;
            g[a].push_back(b), g[b].push_back(a);
        }
        for (int i = 0; i < n; i ++ )
            if (!color[i] && !dfs(i, 1))
                return false;
        return true;
    }
};

[Kaneyang]

思路

图+深度优先搜索DFS

代码

from typing import List
from collections import defaultdict

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        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(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)，其中 E 是 dislikes 的长度。

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

[AtaraxyAdong]

不会做，用答案先打个卡，继续学习。

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;
    }
}

[SunL1GHT]

思路

dfs遍历图

代码

class Solution {
    private boolean flag = true;     
    private boolean[] color;         
    private boolean[] visited;   

    public boolean possibleBipartition(int n, int[][] dislikes) {

        color = new boolean[n + 1];
        visited = new boolean[n + 1];
        List<Integer>[] graph = buildGraph(n, dislikes);

        for (int v = 1; v <= n; v++) {
            if (!visited[v]) {
                dfs(graph, v);
            }
        }
        return flag;
    }

    private List<Integer>[] buildGraph(int n, int[][] dislikes) {
        List<Integer>[] graph = new LinkedList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new LinkedList<>();
        }
        for (int[] edge : dislikes) {

            int v = edge[0];
            int w = edge[1];

            graph[v].add(w);   
            graph[w].add(v);   
        }
        return graph;
    }

    private void dfs(List<Integer>[] graph, int v) {
        if (!flag) return;      
        visited[v] = true;       
        for (int w : graph[v]) {
            if (!visited[w]) {

                color[w] = !color[v];    
                dfs(graph, w);          
            } else {
                if (color[w] == color[v]) {
                    flag = false;
                }
            }
        }
    }
}

[zpc7]

又没有做出来, 只有研究题解了

const possibleBipartition = (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;
};

[uyplayer]

LC 886. 可能的二分法

• 标签： 图
• 难度： 中等

题目大意

给一个dislikes数组，每个元素是相互不喜欢的节点，返回能不能搞成一个数组，不能把两个不喜欢的放在一个数组中

总结

DFS

思路

• DFS

---

DFS

（此处撰写思路）

Golang 代码

    func possibleBipartition(n int, dislikes [][]int) bool {

    graph := make([][]int, n+1)
    for i := 1; i <= n; i++ {
        graph[i] = make([]int, 0)
    }
    //  构造完毕了
    for _, ch := range dislikes {
        x := ch[0]
        y := ch[1]
        graph[x] = append(graph[x], y)
        graph[y] = append(graph[y], x)
    }
    // 颜色
    ok := true
    visited := make([]bool, n+1)
    colors := make([]bool, n+1)
    var dfs func(v int)
    dfs = func(v int) {
        if !ok {
            return
        }
        visited[v] = true
        for _, w := range graph[v] {
            if !visited[w] {
                colors[w] = !colors[v]
                dfs(w)
            } else if colors[v] == colors[w] {
                ok = false
            }
        }

    }

    for i := 1; i <= n; i++ {
        if !visited[i] {
            dfs(i)
        }
    }

    return ok

}

复杂度分析

• 时间复杂度：O(N+E)，E dislikes数组长度
• 空间复杂度：O(N+E)，E dislikes数组长度

[phoenixflyingsky]

最近忙，后面有空了看看题解

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;
    }
}

[findalyzhou]

class Solution {

    int findSet(int[] arr, int a) {
        if (arr[a] == -1) {
            return a;
        }
        return arr[a] = findSet(arr, arr[a]);
    }

    void unionSet(int[] arr, int a, int b) {
        int ai = findSet(arr, a);
        int bi = findSet(arr, b);
        if (ai != bi) {
            arr[ai] = bi;
        }
    }

    public boolean possibleBipartition(int n, int[][] dislikes) {

        List<List<Integer>> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            edges.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < dislikes.length; i++) {
            int[] e = dislikes[i];
            edges.get(e[0] - 1).add(e[1] - 1);
            edges.get(e[1] - 1).add(e[0] - 1);
        }

        int[] bset = new int[n];
        Arrays.fill(bset, -1);

        for (int i = 0; i < n; i++) {
            if (edges.get(i).size() == 0) continue;
            List<Integer> es = edges.get(i);
            int f = es.get(0);
            for (int j = 1; j < es.size(); j++) {
                unionSet(bset, f, es.get(j));
            }
        }

        for (int i = 0; i < n; i++) {
            List<Integer> es = edges.get(i);
            for (int k: es) {
                if (findSet(bset, i) == findSet(bset, k)) return false;
            }
        }

        return true;

    }

}

[LuckyRyan-web]

明天看题解

const possibleBipartition = (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;
};

[acoada]

思路

二分图

代码

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(g, c ^ 1) for g in graph[node])

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

复杂度

• Time: O(N)
• Space: O(N)

[ZOULUFENG]

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