【Day 30 】2021-10-09 - 886. 可能的二分法

[azl397985856]

886. 可能的二分法

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/is-graph-bipartite/

前置知识

• 图的遍历
• 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

[q815101630]

三种方法

今天的题有三种方法解决，DFS，BFS， 并查集

DFS

BFS DFS 来自官方题解 通过这道题理解了DFS 套路，学会了nonlocal使用方法，重点就在于在外层使用for loop后，一但是没有visited 就call dfs。 在dfs中同理，如果visited 那么就检查是否和预期涂色一至。BFS同理。 虽然曾经上过学校算法课但是没有实际代码实现理解不清晰。

#-----------------dfs---------------------
        n = len(graph)
        # Uncolored: 0, RED: 1, GREEN 2
        UNCORLORED, RED,GREEN = 0,1,2
        color = [UNCORLORED]* n
        valid = True

        def dfs(node, c):
            nonlocal valid
            color[node] = c
            cNei = (GREEN if c == RED else RED)

            for neighbor in graph[node]:
                if color[neighbor] == UNCORLORED:
                    dfs(neighbor, cNei)
                    if not valid:
                        return
                elif color[neighbor] != cNei:
                    valid = False
                    return

        # To ensure all cc are colored once 
        for i in range(n):
            if color[i] == UNCORLORED:                                                                      
                dfs(i, RED)
                if not valid:
                    break
        return valid

#-----------------BFS--------------------
        # RED,UNCORLORED,GREEN = -1,0,1
        # n = len(graph)
        # color = [0] * n
        # for i in range(n):
        #     if color[i] == UNCORLORED:
        #         queue = collections.deque()
        #         queue.append(i)
        #         color[i] = RED
        #         while queue:
        #             node = queue.popleft()
        #             cNei = color[node]*-1

        #             for neighbor in graph[node]:
        #                 if color[neighbor] == UNCORLORED:
        #                     color[neighbor] = cNei
        #                     queue.append(neighbor)
        #                 elif color[neighbor] != cNei:
        #                     return False
        # return True   

并查集

这道题可以使用并查集实现，重点在于感觉path遍历所有的node，并把node放入并查集。重点在于，对每一个当前节点的邻节点，让他们join到同一个集合内。

class UnionFind:
    def __init__(self,n):
        self.union = [0]*n
        self.rank = [1]*n
        for i in range(n):
            self.union[i] = i          # the leader of each set is itself

    def find(self, i):
        if self.union[i] == i:
            return i
        self.union[i] = self.find(self.union[i])       # path compression
        return self.union[i]

    def isConnected(self, i, j):
        return self.find(i) == self.find(j)

    def join(self, i, j):
        iHead = self.find(i)
        jHead = self.find(j)
        if iHead == jHead:
            return
        if self.rank[iHead] <= self.rank[jHead]:
            self.union[iHead] = jHead
        else:
            self.union[jHead] = iHead
        if self.rank[iHead] == self.rank[jHead]:
            self.rank[jHead] += 1

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        ds = UnionFind(n)

        for i in range(n):
            for neighbor in graph[i]:
                if ds.isConnected(i, neighbor):
                    return False
                ds.join(graph[i][0], neighbor)
        return True

DFS, BFS 时间, O(V+E), 空间 O(V) 并查集 的时间 O(E log*(V)) 其中， log*V 是介于 O(1) 和O(log(V))中间，具体来源 空间 O(V)

[user1689]

题目

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

思路

无向图染色

python3

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        # time V + E
        # space V + E 
        # 写法一 全局变量
        graph = defaultdict(list)
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)

        uncolor, red, green = 0, 1, 2 
        c = [uncolor for _ in range(n + 1)]
        valid = True

        def dfs(key: int, color: int):
            nonlocal valid
            c[key] = color
            cNei = (green if color == red else red)
            for neighbor in graph[key]:
                if c[neighbor] == uncolor:
                    dfs(neighbor, cNei)
                    if not valid:
                        return
                else:
                    if c[neighbor] != cNei:
                        valid = False
                        return 

        for key, value in graph.items():
            if c[key] == uncolor:
                    dfs(key, red)
                    if not valid:
                        break
        return valid

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        # time V + E
        # space V + E
        # 写法二 check函数

        graph = [[] for _ in range(n + 1)]
        vis = [0 for _ in range(n + 1)]

        for v, u in dislikes:
            graph[v].append(u)
            graph[u].append(v)

        def dfs(node: int, color: int):
            vis[node] = color
            for neighbor in graph[node]:
                if (vis[neighbor] != 0 and vis[neighbor] != -color) or (vis[neighbor] == 0 and not dfs(neighbor, -color)):
                    return False
            return True

        # 一False为False 
        for k in range(1, n + 1):
            if vis[k] == 0 and (not dfs(k, 1)):
                return False
        return True

复杂度分析

• time V + E
• space V + E

相关题目

1. https://leetcode-cn.com/problems/is-graph-bipartite/

[laurallalala]

代码

class Solution(object):
    def possibleBipartition(self, n, dislikes):
        """
        :type n: int
        :type dislikes: List[List[int]]
        :rtype: bool
        """
        g = collections.defaultdict(list)
        for a, b in dislikes:
            g[a].append(b)
            g[b].append(a)
        color = [0] * (n+1)
        for i in range(1, n+1):
            if color[i] != 0:
                continue
            q = collections.deque([i])
            color[i] = 1
            while q:
                cur = q.popleft()
                for dis in g[cur]:
                    if color[dis] != 0:
                        if color[dis] == color[cur]:
                            return False
                    else:
                        color[dis] = -color[cur]
                        q.append(dis)
        return True

复杂度

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

[itsjacob]

Intuition

• graph binary coloring problem
• graph is implemented using adjancency list
• we can use additional visited array to record the vertex has been colored or not, or simply encode color 0 for un-colored status
• either dfs or bfs can work

Implementation

class Solution
{
public:
  bool possibleBipartition(int n, vector<vector<int>> &dislikes)
  {
    // create the graph with adjancenty list
    std::vector<std::vector<int>> adjList(n + 1);
    for (auto const &dislike : dislikes) {
      adjList[dislike[0]].push_back(dislike[1]);
      // undirected graph so update both vertices
      adjList[dislike[1]].push_back(dislike[0]);
    }

    // 0: uncolored; 1: group 1 color; 2: group 2 color
    std::vector<int> colors(n + 1, 0);
    for (int ii = 1; ii <= n; ii++) {
      if (colors[ii] == 0) {
        if (!dfs(adjList, colors, ii, 1)) return false;
      }
    }
    return true;
  }

private:
  // @return  whether the vertex and its neighbors can be colored into two categories
  bool dfs(std::vector<std::vector<int>> &adjList, std::vector<int> &colors, int cur, int color)
  {
    colors[cur] = color;
    for (auto const &neighbor : adjList[cur]) {
      // conflicts in neighors
      if (colors[neighbor] == color) {
        return false;
      }
      // uncolored neighbor, color it with a different color
      if (colors[neighbor] == 0) {
        if (!dfs(adjList, colors, neighbor, -color)) return false;
      }
    }
    return true;
  }
};

Complexity

• Time complexity: O(n+m), n is the number of vertices, m is the number of edges
• Space complexity: O(n+m)

[zjsuper]

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        graph = [[0] * n for i in range(n)]
        colors = [0] * n
        for i,j in dislikes:
            graph[i-1][j-1] =1
            graph[j-1][i-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

[leungogogo]

LC886. Possible Bipartition

Method. BFS

Main Idea

Basically, this problem is asking if we can mark the graph with 2 colors, where adjacent vertices can't have the same color.

So we can apply BFS to traverse the graph, say we mark a vertex v with color 1, then we have to mark all its neighbors with color 2. If any of them was marked color 1, then we know it's impossible to mark the graph with 2 colors, so we can return false.

If no such contradictions found, that means the graph can be 2-colored, so return true.

Code

• Java

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

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

        int[] colors = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            if (colors[i] != 0) continue;
            Queue<Integer> q = new ArrayDeque<>();
            q.offer(i);
            colors[i] = 1;
            while (!q.isEmpty()) {
                int size = q.size();
                while (size-- > 0) {
                    int v = q.poll(), c = colors[v];
                    for (int nei : graph[v]) {
                        if (colors[nei] == c) return false;
                        if (colors[nei] != 0) continue;
                        colors[nei] = -1 * c;
                        q.offer(nei);
                    }
                }
            }
        }
        return true;
    }
}

Complexity Analysis

Time: O(E + V)

Space: O(E + V)

[watermelonDrip]

class Solution:

    def isBipartite(self, graph: List[List[int]]) -> bool:
        # 初始化 bigraph
        n = len(graph)

        bigraph = [[0]*n for _ in range(n)]
        # create bigraph
        for i in range(n):
            for j in graph[i]:
                bigraph[i][j] = 1

        # 开始着色
        # 初始着色list: colors; 0: no coloring 

        colors = [0]*n

        for k in range(n):
            # k节点以着色，如果没有就开始涂色
            if colors[k] == 0 and not self.dfs(bigraph,colors,k,1,n):
                return False
        return True
    def dfs(self, bigraph, colors , i, color,n):
        # 从i 点开始着色
        colors[i] = color
        # 访问每一个跟i有连通的节点
        for j in range(n):
            # 找到一个连通点j
            if bigraph[i][j] == 1:
                if colors[j] == color:
                    # 如果跟i点涂色一样， 则冲突,两个节点来自同一个集合
                    return False
                if colors[j] == 0 and not self.dfs(bigraph,colors,j,-1*color,n):
                    return False
        return True

[james20141606]

Day 30: 886. Possible Bipartition (graph, bipartite, DFS)

• Problem Link

  • 886. Possible Bipartition

• Ideas

  • It is same with 785. Is Graph Bipartite?
  • Sol 1: it is easy to see that the problem asks that if the graph is bipartite graph. And we could easily find that the necessary and sufficient condition is that the graph could not have odd length cycles. The detailed proof is https://proofwiki.org/wiki/Graph_is_Bipartite_iff_No_Odd_Cycles. # Time complexity: O(|V| + |E|); Space complxity: O(|V|). (|V| = N, |E| = len(dislikes)).
  • Sol 2: use coloring + DFS. We could construct the graph, and use coloring method to color each vertex. We loop through all the dislike pairs, the vertex could be in three state: -1, 1 (representing two groups) and 0 (meaning the state has not been assigned at least once). So we know that for each vertex, if it is 1/-1, we could not flip its value, or it means it will belong to two groups and thus the bipartition will not hold. Time complexity: O(|V| + |E|); Space complxity: O(|V|^2)
  • Sol 3: similarly, but we only use two states, we did not use 0 to represent initial state without coloring but use color={} to record if the node is seen and colored. We check the color state if it is already colored, then color the node, and return the bool state of all the node_ connected with node. Use list or dict to loop through dislike to create sparse adjacency matrix so that the time and space complexity could both be O(V+E)

• Complexity: hash table and bucket

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

• Code

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        neighbor_list = [[] for _ in range(n)]
        #this will create a sparse nested list for the adjacency graph
        for dislike in dislikes:
            # The vertex index starts from "0".
            neighbor_list[dislike[0] - 1].append(dislike[1] - 1)
            neighbor_list[dislike[1] - 1].append(dislike[0] - 1)
        def isOddCyclic(curr, parent, path, path_len, visited):
            """Detects if the undirected graph has an odd cycle."""
            visited[curr] = True
            # path = the dict from the vertex to its index in the "path".
            path[curr] = path_len
            for neighbor in neighbor_list[curr]:
                if not visited[neighbor]:
                    # Recursively check if the neighbor has an odd cycle.
                    if isOddCyclic(neighbor, curr, path, path_len + 1, visited):
                        return True
                elif neighbor != parent:
                    # If we see a vertex other than the parent, we have found a cycle.      
                    if neighbor in path and (path_len - path[neighbor]) % 2 == 0:
                        return True
            path.pop(curr)
            return False

        path = {}
        visited = [False] * n
        for i in range(n):
            if not visited[i] and isOddCyclic(i, -1, path, 0, visited):
                return False
        return True

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

class Solution(object):
    def possibleBipartition(self, N, dislikes):
        #dict to create sparse adjacency matrix, space for the dict becomes O(V)
        graph = collections.defaultdict(list)
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)
        #print (graph)

        color = {}
        def dfs(node, c = 0):
            #print ('c',c, node)
            if node in color:
                return color[node] == c  #if the node is already colored, check if it is the same or reversed
            color[node] = c  #coloring
            return all(dfs(node_, c ^ 1) for node_ in graph[node]) #check the neighbors of node's state, and color them by `c^1` to reverse the color
        return all(dfs(node) for node in range(1, N+1) if node not in color)
        #check if all nodes satisfy conditions

• other resources:
  • 785. Is Graph Bipartite?
  • https://proofwiki.org/wiki/Graph_is_Bipartite_iff_No_Odd_Cycles
  • https://leetcode.com/problems/possible-bipartition/discuss/160371/Python-Decide-if-a-graph-is-bipartite-by-checking-the-existence-of-odd-cycles.
  • https://leetcode-cn.com/problems/possible-bipartition/solution/ke-neng-de-er-fen-fa-by-leetcode/
  • union and find set: https://zhuanlan.zhihu.com/p/93647900

[biancaone]

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

        graph = self.build_graph(dislikes)
        colors = [0 for _ in range(n + 1)]

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

        return True

    def build_graph(self, dislikes):
        graph = collections.defaultdict(list)
        for pair in dislikes:
            graph[pair[0]].append(pair[1])
            graph[pair[1]].append(pair[0])

        return graph

    def dfs(self, graph, colors, index, color):
        colors[index] = color
        for neighbor in graph[index]:
            if colors[neighbor] == color:
                return False

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

        return True

[Daniel-Zheng]

思路

DFS。

代码(C++)

class Solution {
public:
    bool paint(int x, int c, vector<vector<int>>& edges, vector<int>& colors) {
        if (colors[x] == c) return true;
        else if (colors[x] != 0 && colors[x] != c) return false;
        colors[x] = c;
        int reversed = (c == 1 ? 2 : 1);
        for (auto& e : edges[x]) {
            if (!paint(e, reversed, edges, colors)) {
                colors[x] = 0;
                return false;
            }
        }
        return true;
    }
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        vector<vector<int>> edges(N);
        for (auto e : dislikes) {
            edges[e[0]-1].push_back(e[1]-1);
        }
        vector<int> colors(N, 0);
        for (int i = 0; i < N; ++i) {
            if(!paint(i, 1, edges, colors) && !paint(i, 2, edges, colors)) {
                return false;
            }
        }
        return true;
    }
};

复杂度分析

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

[ai2095]

LC886. Possible Bipartition

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

Topics

• Graph
• DFS

Similar Questions

Hard

Medium

• https://leetcode.com/problems/find-leaves-of-binary-tree/
• https://leetcode.com/problems/validate-binary-tree-nodes/
• https://leetcode.com/problems/detect-cycles-in-2d-grid/

思路

DFS and check cycle.

代码 Python

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        def dfs(idx, layer):
            nonlocal visited, adj_list  
            if visited[idx] != -1:
                return abs(layer - visited[idx]) % 2 == 0 

            visited[idx] = layer
            for neib in adj_list[idx]:
                if not dfs(neib, layer + 1):
                    return False
            return True

        # prepare adjacent list
        adj_list = defaultdict(list)
        for e in dislikes:
            adj_list[e[0]].append(e[1])
            adj_list[e[1]].append(e[0])
        visited = [-1] * (n + 1)

        for i in range(1, n+1):
            layer = visited[i] if visited[i] > -1 else 0
            if not dfs(i, layer):
                return False

        return True

复杂度分析

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

[Laurence-try]

思路

DFS 图遍历

代码

class Solution:
    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

    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

复杂度分析 时间复杂度：O(m+n) 空间复杂度：O(n^2)

[cicihou]

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

        def dfs(graph, colors, i, color):
            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 dfs(graph, colors, j, -1 * color):
                        return False
            return True

        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 dfs(graph, colors, i, 1):
                return False
        return True

这道题太难了，不会做

[lxy030988]

思路

• 循环+深度优先递归

代码 js

/**
 * @param {number} n
 * @param {number[][]} dislikes
 * @return {boolean}
 */
var possibleBipartition = function (n, dislikes) {
  //把每个人不喜欢的人存到二维数组里
  const temp = new Array(n).fill(-1).map(() => new Array()),
    colors = Array(n).fill(-1)

  for (const dislike of dislikes) {
    temp[dislike[0] - 1].push(dislike[1] - 1)
    temp[dislike[1] - 1].push(dislike[0] - 1)
  }

  // console.log('temp', temp)

  // colors对所有人进行分组 0 和 1
  const dfs = (cur, color) => {
    colors[cur] = color
    //temp[cur] 当前用户不喜欢的人
    for (let dis of temp[cur]) {
      if (colors[dis] !== -1 && colors[dis] === color) {
        //不喜欢的人 已经被分组了  并且分组和当前用户相同
        return false
      }
      if (colors[dis] === -1 && !dfs(dis, color == 0 ? 1 : 0)) {
        //不喜欢的人没有被分组  继续递归
        return false
      }
    }
    return true
  }

  for (let i = 0; i < n; i++) {
    //循环遍历每个人的情况 有一个人不符合条件 就返回false
    if (colors[i] === -1 && !dfs(i, 0)) {
      return false
    }
  }

  return true
}

复杂度分析

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

[septasset]

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

[ZhuMengCheng]

bfs + 染色法

var isBipartite = function (graph) {
    const len = graph.length;
    const colors = new Array(len).fill(0); 
    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+M) 空间复杂度: O(N)

[Jinjin680]

思路

• 所有的人被分到两个组，组内的人不可以讨厌组内的人，属于二分图（二分图中的结点可以被分成两个独立的集合，图中的每条边连接的两个结点属于不同的集合）
• 用染色法来表示是否已经分组
• 遍历每个人，若未分组过，对其进行分组
  • 遍历这个人讨厌的人，给他们分组，若这个人讨厌的人与他在同一个组，则返回false

代码（C++）

class Solution {
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        vector<vector<int>> adj(n + 1);
        for(int i = 0; i < dislikes.size(); i++){
            adj[dislikes[i][0]].push_back(dislikes[i][1]);
            adj[dislikes[i][1]].push_back(dislikes[i][0]);
        }

        queue<int> q;
        vector<int> color(n + 1, -1);
        for(int i = 1; i <= n; i++){
            if(color[i] != -1) continue; //已经分好组的不必再分组
            q.push(i);
            color[i] = 0;
            while(!q.empty()){
                int curr = q.front();
                q.pop();
                for(int ele : adj[curr]){
                    if(color[ele] == color[curr]) return false;
                    if(color[ele] == -1){
                        color[ele] = 1 - color[curr];
                        q.push(ele);
                    }
                }
            }
        }
        return true;
    }
}; 

复杂度分析

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

[chenming-cao]

解题思路

DFS, 染色法。根据题目信息建立邻接表来表示图。然后进行DFS，看每条边相邻两个点是否都能够染上不同颜色（颜色表示：0表示为染色，1表示染红色，-1表示染蓝色，变到相反颜色乘-1即可）。

代码

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

    private boolean dfs(int node, int color) {
        if (colors[node] != 0) return colors[node] == color;
        colors[node] = color;
        for (int next: graph[node]) {
            if (colors[next] == 0 && !dfs(next, -color)) return false;
            if (colors[next] == color) return false;
        }
        return true;
    }
}

复杂度分析

• 时间复杂度：O(n + m)，n为顶点数，m为边数
• 空间复杂度：O(n + m)，使用邻接表

[learning-go123]

思路

• dfs 染色法来自官方题解

代码

• 语言支持：Go

Go Code:

func possibleBipartition(n int, dislikes [][]int) bool {
    g := make([][]int, n)
    for i := 0; i < n; i++ {
        g[i] = make([]int, n)
    }
    for _, val := range dislikes {
        i, j := val[0]-1, val[1]-1
        g[i][j] = 1
        g[j][i] = 1
    }

    colors := make([]int, n)
    var dfs func(int, int) bool
    dfs = func(i, color int) bool {
        colors[i] = color
        for j := 1; j < n; j++ {
            if g[i][j] != 1 {
                continue
            }

            if colors[j] == color {
                return false
            }

            if colors[j] == 0 && !dfs(j, -color) {
                return false
            }
        }
        return true
    }

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

    return true
}

复杂度分析

令 n 为数组长度。

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

[leolisgit]

思路

题目就是求是否可以把所有的节点划分为两个组，使得相邻节点在不同的组。 BFS + 染色法，对每一个节点，赋予一个颜色， 然后相邻的点赋予另一个颜色，直到找到一个相邻已经染色的节点和该节点颜色相同，就违反了规则。

代码

class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        // construct graph
        List<Integer>[] 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]);
        }

        int[] color = new int[n + 1];

        // add color
        for (int i = 1; i <= n; i++) {
            if (color[i] != 0) continue;

            Queue<Integer> q = new LinkedList<>();
            q.offer(i);
            color[i] = 1;
            while (!q.isEmpty()) {
                int size = q.size();
                while (size-- > 0) {
                    int v = q.poll();
                    int c = color[v];
                    for (int neighbor : graph[v]) {
                        if (color[neighbor] == c) return false;
                        if (color[neighbor] != 0) continue;
                        color[neighbor] = -1 * c;
                        q.offer(neighbor);
                    }
                }
            }
        }
        return true;      
    }
}

复杂度

时间：O(v + e) 空间：O(v + e)

[RocJeMaintiendrai]

题目

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

思路

先使用hashmap来构建一个图，然后对于每一个node进行染色，将一个借点涂为红色的话，再将他邻居涂为蓝色，再将邻居的邻居涂为红色，当遇到已经有了颜色但是要涂不同颜色的情况即发生了冲突，此时即不能分为两组。

代码

class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        for(int[] d : dislikes) {
            int a = d[0];
            int b = d[1];
            graph.putIfAbsent(a, new HashSet<>());
            graph.putIfAbsent(b, new HashSet<>());
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

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

    private boolean dfs(int[] colors, int color, int node, Map<Integer, Set<Integer>> graph) {
        if(colors[node] != 0) {
            return colors[node] == color;
        }
        colors[node] = color;
        if(graph.get(node) == null) return true;
        for(int next : graph.get(node)) {
            if(!dfs(colors, -color, next, graph)) {
                return false;
            }
        }
        return true;
    }
}

复杂度分析

时间复杂度

O(N + M) M是dislike数组的长度

空间复杂度

O(N + M)

[carsonlin9996]

1. 构无向图
2. BFS 并且分组图， 如果bfs途中遇到任何邻居是同样组的， return false
3. 每一层bfs 更换组的信息

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

        Map<Integer, ArrayList<Integer>> graph = new HashMap<>();
        //初始化
        for (int i = 1; i < n + 1; i++) {
            graph.put(i, new ArrayList<Integer>());
        }
        //构图
        for (int[] pair : dislikes) {
            graph.get(pair[0]).add(pair[1]);
            graph.get(pair[1]).add(pair[0]);
        }

        int[] groups = new int[n + 1]; //unknown: 0, group1: 1, group2: -1;

        Queue<Integer> queue = new ArrayDeque<>();

        for (int i = 1; i < n + 1; i++) {
            if (groups[i] != 0) {
                //已经分组过
                continue;
            }
            queue.offer(i);
            groups[i] = 1;

            while (!queue.isEmpty()) {
                int cur = queue.poll();

                for (int neighbor : graph.get(cur)) {

                    if (groups[neighbor] == groups[cur]) {
                        return false;
                    }
                    if (groups[neighbor] != 0) {
                        continue;
                    }
                    groups[neighbor] = -groups[cur];
                    queue.offer(neighbor);
                }
            }
        }
        return true;
    }
}

加个DFS
class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {

        Map<Integer, ArrayList<Integer>> graph = new HashMap<>();
        //初始化
        for (int i = 1; i < n + 1; i++) {
            graph.put(i, new ArrayList<Integer>());
        }
        //构图
        for (int[] pair : dislikes) {
            graph.get(pair[0]).add(pair[1]);
            graph.get(pair[1]).add(pair[0]);
        }

        int[] groups = new int[n + 1]; //unknown: 0, group1: 1, group2: -1;

        for (int i = 1; i < n + 1; i++) {

            if (groups[i] == 0 && !dfs(i, 1, graph, groups)) {
                return false;
            }
        }

        return true;

    }

    private boolean dfs(int cur, int color, Map<Integer, ArrayList<Integer>> graph, int[] groups) {

        groups[cur] = color;

        for (int neighbor : graph.get(cur)) {
            if (groups[neighbor] == color) {
                return false;
            }
            if (groups[neighbor] == 0 && !dfs(neighbor, -color, graph, groups));
        }
        return true;
    }
}

[muimi]

思路

题目中分成两组，产生三种状态（分到红组1，分到蓝组-1，尚未分组0）
根据dislikes数组，为每一个节点构建一个dislike的list，遍历每个节点验证是否有解

代码

class Solution {
  public boolean possibleBipartition(int n, int[][] dislikes) {
    // 0: not colored, 1: colored by red, -1: colored by blue
    int[] colorTable = new int[n + 1];
    // create graph
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
    for (int[] edge : dislikes) {
      graph.get(edge[0]).add(edge[1]);
      graph.get(edge[1]).add(edge[0]);
    }
    // judge
    for (int i = 1; i <= n; i++) {
      if (colorTable[i] == 0 && !dfs(graph, colorTable, i, 1)) return false;
    }
    return true;
  }
  private boolean dfs(List<List<Integer>> graph, int[] colorTable, int cur, int color) {
    colorTable[cur] = color;
    for (int next : graph.get(cur)) {
      if (colorTable[next] == color) return false;
      if (colorTable[next] == 0 && !dfs(graph, colorTable, next, -color)) return false;
    }
    return true;
  }
}

复杂度

• 时间复杂度：O(N)，每个节点访问一次
• 空间复杂度：O(N)

[ginnydyy]

Problem

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

Notes

• Use graph
• To build the graph
  • Can use an array of ArrayList, to represent all the neighbors of each person.
  • The edges of the graph is based on the dislikes array, each array item represents the dislike relation between two persons, and the relation should be bidiretional.
• To validate whether the group of people can be divided into two groups
  • Can use bipartition
  • Traverse the graph
  • if the node is not colored, then color it with 0 (red). And keep coloring the neighbors with 1 (blue), and the neighbors' neighbors' with 0 (red), and so on. If any person is colored and the color is different from the currently attempted color, that means a conflict, and return false immediatly.
  • if the node is colored, then check the colorMap, if the existing color is different from the currently attempted color, return false immeditaly.
  • After traversing the graph, if no conflict happened, then return true. The group of the people can be divided into two groups.

Solution

class Solution {
    ArrayList[] graph;
    Map<Integer, Integer> colorMap = new HashMap<>();

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

        // build the graph as per the dislikes array
        for(int i = 1; i <= N; i++){
            graph[i] = new ArrayList<Integer>();
        }

        // it's bidirectional
        for(int[] edge: dislikes){
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }

        for(int i = 1; i <= N; i++){
            if(!colorMap.containsKey(i) && !dfs(i, 0)){
                return false;
            }
        }

        return true;
    }

    private boolean dfs(int i, int color){
        if(colorMap.containsKey(i)){
            return colorMap.get(i) == color;
        }

        colorMap.put(i, color);

        List<Integer> neighbors = graph[i];
        for(int neighbor: neighbors){
            if(!dfs(neighbor, color ^ 1)){
                return false;
            }
        }

        return true;
    }
}

Compleixty

• Time: O(n + e) each person will be only colored once, each edge will be only validated once (n is the number of people, e is the length of the dislike array).
• Space: O(n + e) n is for the color map, 2e is for the graph, total O(n + 2e) => O(n + e).

[StefanLeeee]

思路

深度优先遍历

代码

class Solution {
    ArrayList<Integer>[] graph;// 使用邻接表存储图
    Map<Integer,Integer> color;//记录上色结果
    public boolean possibleBipartition(int N, int[][] dislikes) {
        graph=new ArrayList[N+1];// 0位其实不用,使用的使1~N位
        //ArrayList实例化
        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++) {// 对该组N人遍历
            if(!color.containsKey(node)) {// 还未上色
                boolean OK=dfs(node,0);//从node开始深度遍历
                if(!OK) return false; 
            }else continue;//已经上色
        }
        return true;
    }
    private boolean dfs(int node, int c) {
        //从possibleBipartition调用时node是未上色的
        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+E)，其中 EE 是 dislikes 的长度。
• 空间复杂度：O(N+E)

[xjlgod]

class Solution {
    List<Integer>[] graph;
    HashMap<Integer, Integer> colors;

    public boolean possibleBipartition(int n, int[][] dislikes) {
        // 涉及到泛型擦除的知识点
        graph = new List[n + 1];
        // ArrayList实例化
        for (int i = 0; i !=n+1; i++) {
            graph[i]=new ArrayList<Integer>();
        }
        for (int[] dislike : dislikes) {
            graph[dislike[0]].add(dislike[1]);
            graph[dislike[1]].add(dislike[0]);
        }
        colors = new HashMap();
        // 从每个点出发的联通变量是否有问题。
        for (int i = 1; i <= n; i++) {
            if (!colors.containsKey(i)) {
                boolean ok = dfs(i, 0);
                if (!ok) {
                    return false;
                }
            } else {
                continue;
            }
        }
        return true;
    }

    public boolean dfs(int i, int color) {
        // 如果之前染过色，则看染色是否正确。
        if (colors.containsKey(i)) {
            int originColor = colors.get(i);
            if (originColor != color) {
                return false;
            } else {
                return true;
            }
        }
        colors.put(i, color);
        // 继续深度遍历
        for (int end : graph[i]) {
            boolean ok = dfs(end, color ^ 1);
            if (!ok) {
                return false;
            }
        }
        return true;
    }
}

[peteruixi]

思路

将所给出的图案分成两个组, 给出的不喜欢关系得出, 两个节点不能在同一个组. 主要任务分为:

1. 构建无向图
2. 使用dfs遍历

代码

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;++i){
            graph[i] = new ArrayList();
        }
        for( int[] edges : dislikes){
            graph[edges[0]].add(edges[1]);
            graph[edges[1]].add(edges[0]);
        }

         /* dfs */
        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 src, int group){
        /* 获取当前节点颜色, 假如当前节点颜色跟上级节点一致返回false*/
        if (color.containsKey(src)){
            return color.get(src) == group;
        }

        /*未上色*/
        color.put(src,group);
        for (int nei: graph[src])
            if (!dfs(nei, group ^ 1)) //因为不喜欢, 所以邻居处于不同组
                return false;
        return true;

    }
}

复杂度分析

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

[RonghuanYou]

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        edge = [[] for _ in range(n + 1)]
        for u, v in dislikes:
            edge[u].append(v)
            edge[v].append(u)

        color = [0] * (n + 1)
        for i in range(1, n + 1):
            if color[i] == 0:
                q = [i]
                color[i] = 1
                while q:
                    cur = q.pop()
                    cur_color = color[cur]
                    for node in edge[cur]:
                        # 没有颜色，涂成相反的颜色
                        if color[node] == 0:
                            color[node] = cur_color * -1
                            q.append(node)
                        # 有颜色了，并且颜色相同，冲突
                        elif color[node] == cur_color:
                            return False
        return True

[chaggle]

---

title: "Day 30 886. 可能的二分法" date: 2021-10-09T15:36:22+08:00 tags: ["Leetcode", "c++", "graph"] categories: ["91-day-algorithm"] draft: true

---

886. 可能的二分法

题目

给定一组 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

题目思路

• 1、经典并查集

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

复杂度

• 时间复杂度：O(n)

• 空间复杂度：O(n)

[zszs97]

开始刷题

题目简介

【Day 29 】2021-10-08 - 997. 找到小镇的法官

题目思路

• DFS

题目代码

代码块

class Solution {
public:
    bool paint(int x, int c, vector<vector<int>>& edges, vector<int>& colors) {
        if (colors[x] == c) return true;
        else if (colors[x] != 0 && colors[x] != c) return false;
        colors[x] = c;
        int reversed = (c == 1 ? 2 : 1);
        for (auto& e : edges[x]) {
            if (!paint(e, reversed, edges, colors)) {
                colors[x] = 0;
                return false;
            }
        }
        return true;
    }
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        vector<vector<int>> edges(N);
        for (auto e : dislikes) {
            edges[e[0]-1].push_back(e[1]-1);
        }
        vector<int> colors(N, 0);
        for (int i = 0; i < N; ++i) {
            if(!paint(i, 1, edges, colors) && !paint(i, 2, edges, colors)) {
                return false;
            }
        }
        return true;
    }
};

复杂度

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

[chen445]

代码

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        if n==1:
            return True
        graph={}
        for dislike in dislikes:
            if dislike[0] not in graph:
                graph[dislike[0]]=[]
            if dislike[1] not in graph:
                graph[dislike[1]]=[]
            graph[dislike[0]].append(dislike[1])
            graph[dislike[1]].append(dislike[0])
        UNASSIGNED,RED,BLUE=0,1,-1
        people=[UNASSIGNED]*(n+1)
        def dfs(person,color):
            if people[person] != UNASSIGNED:
                return people[person] == color 
            people[person]=color
            if person not in graph:
                return True
            for other in graph[person]:
                if not dfs(other,-color):
                    return False
            return True
        for person in range(1,len(people)):
            if people[person] == UNASSIGNED:
                if not dfs(person,RED):
                    return False
        return True

复杂度

Time: O(E+V)

Space: O(n^2)

[Huangxuang]

题目：886. Possible Bipartition

思路

• 先建立个图，是个无方向的，用2darray即可
• dfs遍历不会，得再想想

代码

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

作者：LeetCode
链接：https://leetcode-cn.com/problems/possible-bipartition/solution/ke-neng-de-er-fen-fa-by-leetcode/

[newbeenoob]

思路

---

染色判定二分图的模板题 ： 首先为题目的dislike 关系建图，dislike[i] = [a , b] 代表 a b 之间有一条邻接的边 定义 visit 数组并初始化为全0，代表未访问，两种颜色使用 1 , -1 表示，首先从任何一个未被访问的顶点为起始点开始染色，对相邻的顶点染不同的颜色，如果遇到某一顶点与其邻点同色，代表该图不是二分图。

如果所有顶点都被染色成功，代表这是一个二分图

代码：JavaScript

做法：DFS （ 并查集的做法后续补上

var possibleBipartition = function(N, dislikes) {

    // 建图
    const graph = new Array(N).fill(0).map(x => new Array());

    for(const [fr , to] of dislikes) {
        graph[fr - 1].push(to - 1);
        graph[to - 1].push(fr - 1);
    }

    // 初始化
    const visit = new Array(N).fill(0);

    const dfs = (i , g , color , visit) => {

        visit[i] = color;

        // 检查邻边 染色
        for(const adj of g[i]) {
            if(!visit[adj]) {
                if(!dfs(adj , g , -color , visit)) return false;
            }else if(color === visit[adj]){
                return false;
            }
        }
        return true;

    }

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

    return true;
};

---

复杂度分析

---

• 时间复杂度： O(V + E) v 为无向图的顶点个数，E 为无向图的边个数

• 额外空间复杂度： O(V)

标签

---

图 ， 深度优先搜索 , 广度优先搜索 , 并查集

[kennyxcao]

886. Possible Bipartition

Intuition

• DFS and look for any inconsistency in blue/red coloring

Code

/**
 * @param {number} n
 * @param {number[][]} dislikes
 * @return {boolean}
 */
const possibleBipartition = function(n, dislikes) {
  const [UNVISITED, BLUE, RED] = [-1, 0, 1];
  const graph = Array.from({length: n + 1}, () => new Set());
  for (const [a, b] of dislikes) {
    graph[a].add(b);
    graph[b].add(a);
  }
  const colors = Array(n + 1).fill(UNVISITED);
  for (let node = 1; node <= n; ++node) {
    if (colors[node] === UNVISITED && !paint(graph, colors, node, BLUE)) {
      return false;
    }
  }
  return true;

  function paint(graph, colors, node, color) {
    if (colors[node] !== UNVISITED) return colors[node] === color;
    colors[node] = color;
    const oppsiteColor = color === BLUE ? RED : BLUE;
    for (const neighbor of graph[node]) {
      if (!paint(graph, colors, neighbor, oppsiteColor)) return false;
    }
    return true;
  }
};

Complexity Analysis

• Time: O(V+E)
• Space: O(V^2)
• V = num of vertices
• E = num of edges

[Okkband]

class Solution {
private:
    vector<int> color; // 存储每个节点的颜色
    bool valid; //最终的返回值
    // 参数：graph, 当前节点要染色的颜色，当前节点的索引
    void dfs(const vector<vector<int>>& graph, const int clr, const int idx){
        color[idx] = clr; // 将当前节点染色
        int new_color = (clr == 1 ? 2: 1); // 计算邻居的颜色，邻居的颜色应该和当前的颜色不同
        vector<int> neighbor = graph[idx]; // 获取当前节点的邻居s
        for (int i=0; i<neighbor.size(); i++){
            if (color[neighbor[i]] == 0){ // 如果邻居未染色，则dfs，并且染色
                dfs(graph, new_color, neighbor[i]);
                if (!valid) return; // 检测是否valid， 提前终止
            } else if (color[neighbor[i]] != new_color){ // 如果邻居已经染色并且和要染色的颜色不同，说明冲突
                valid = false;
                return;
            }
        }
    }
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        valid = true;
        color.assign(n, 0);
        for (int i=0; i<n; i++){
            // 遍历图的每个节点，如果为染色，则dfs
            if (color[i] == 0){
                // dfs，将当前节点染色为红色
                dfs(graph, 2, i);
            }
        }
        return valid;
    }
};

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

空间负责度：O(N)

[machuangmr]

题目886. 可能的二分法

思路：参考官方题解

• 图的题目不太会。。。

  代码

  class Solution {
  ArrayList<Integer>[] graph;// 使用邻接表存储图
  Map<Integer,Integer> color;//记录上色结果
  public boolean possibleBipartition(int n, int[][] dislikes) {
      graph=new ArrayList[n+1];// 0位其实不用,使用的使1~N位
      //ArrayList实例化
      for (int i = 0; i <= n; 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;node++) {// 对该组N人遍历
          if(!color.containsKey(node)) {// 还未上色
              boolean OK=dfs(node,0);//从node开始深度遍历
              if(!OK) return false; 
          }
      }
      return true;
  }
  private boolean dfs(int node, int c) {
      //从possibleBipartition调用时node是未上色的
      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 + E), E是 是 dislikes 的长度。
• 空间复杂度：O(n)

[carterrr]

public class 判断二分图_785 { public boolean isBipartite_dfs(int[][] graph) { // 0表示点未访问 1和-1表示两种颜色 int[] visited = new int[graph.length]; for(int i = 0; i < graph.length; i++) { // 依据题意 可能不是联通图 因此需要每个都来染色 // 不连通的孤岛直接染色成1即可 如果能够在这个连通子分量里面成功染色 也是可以分的 if(visited[i] == 0 && dfs(graph, visited, i, 1)) { return false; } } return true; }

private boolean dfs(int[][] graph, int[] visited, int i, int color) {
    if(visited[i] != 0) {  // 本子连通图内部之前访问过该节点
        //  节点 A自身是 -1 相邻节点B应该染色成-1  但是之前是1 说明AB同色  一条边的相邻节点只能放到一个集合里
        // 返回true  表示有异常
        return visited[i] != color;
    }
    // 未染色过
    visited[i] = color;
    for(int t : graph[i]) { // 对该节点的连通节点  染上相反的颜色  如果任何一个之前染色过且颜色相同
        if(dfs(graph, visited, t, -color)) {
            return true;
        }
    }
    return false;
}

public boolean isBipartite_bfs(int[][] graph) {
    int[] visited = new int[graph.length]; // 0表示点未访问  1和-1表示两种颜色
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < graph.length; i++) {
        if(visited[i] != 0) continue;
        queue.offer(i);  visited[i] = 1; // 第一个节点染色
        // 对每个节点 取得其邻居
        // 如果没颜色就染色并塞进来 下一轮判断其相邻点
        // 如果有颜色判断是否颜色不对  如果不对就返回异常
        while (!queue.isEmpty()) {
            Integer node = queue.poll();
            int color = visited[node];
            int neighborColor = - color;

            for (int neighbor : graph[node]) {
                int neighborCurColor = visited[neighbor];
                if(neighborCurColor == 0) {
                    visited[neighbor] = neighborColor;
                    queue.offer(neighbor);
                } else {
                    if(neighborCurColor != neighborColor) {
                        return false;
                    }
                }
            }

        }
    }
    return true;
}

public boolean isBipartite_unionFind(int[][] graph) {
    UnionFind uf = new UnionFind(graph.length);
    // 遍历每个顶点  判断是否之前就已经将该点合并到了其邻接点集中  说明这个点无法和邻接点集分开成两个集合
    for (int i = 0; i < graph.length; i++) {
        for (int j : graph[i]) {
            if(uf.isConnected( i, j)) return false;
            uf.union(graph[i][0], j);  // 临接点合并为同一个根  这些点组成一个集合
        }
    }
    return true;
}

class UnionFind {
    int[] uf;
    public UnionFind(int size) {
        uf = new int[size];
        for(int i = 0; i< size; i++) {
            uf[i] = i; // 每个点的根默认初始化为自身
        }
    }

    /**
     * 把一个节点的根赋值给另一个节点的根
     * @param p 
     * @param q
     */
    public void union(int p, int q) {
        uf[find(p)] = find(q);
    }

    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    /**
     * 查找一个节点的根
     * @param p
     */
    private int find(int p) {
        if(uf[p] == p) return p;
        return uf[p] = find(uf[p]); // 不等就递归find自身的root 并把等的root返回回去赋值给 uf[p]
    }
}

}

[Cartie-ZhouMo]

代码

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

[LareinaWei]

Thinking

Referring to the solution, we construct a graph using the dislike array. And fine nodes that have edge between them cannot in the same group. We can use a hashmap (array) to store the value of each person's group.

Code

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

        colors = [0 for _ in range(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 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

Complexity

Time complexity: O(n).
Space complexityL O(n).

[KennethAlgol]

class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        List<List<Integer>> notSameGroupList = new ArrayList<>();
        for (int i = 0; i <= n; i++) notSameGroupList.add(new ArrayList<>());

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

        int[] colors = new int[n + 1];

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

    private boolean dfs(List<List<Integer>> list, int i, int color, int[] colors){
        colors[i] = color;

        for (int next : list.get(i)){
            if (colors[next] == -color) continue; 
            if (colors[next] == color || !dfs(list, next, -color, colors)) return false;
        }
        return true;
    }
}

[JinhMa]

class Solution { ArrayList[] 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;
}

}

[potatoMa]

思路

---

先遍历dislikes找出所有人的邻居，然后从第一个人开始染色，并将其所有邻居染成相反的颜色，当出现冲突时，则说明不成立。

代码

---

JavaScript Code

/**
 * @param {number} n
 * @param {number[][]} dislikes
 * @return {boolean}
 */
var possibleBipartition = function(n, dislikes) {
    const arr = new Array(n + 1);
    for (const [a, b] of dislikes) {
        if (!arr[a]) {
            arr[a] = [b];
        } else {
            arr[a].push(b);
        }
         if (!arr[b]) {
            arr[b] = [a];
        } else {
            arr[b].push(a);
        }
    }
    const color = new Map();
    function dfs(i, c) {
        if (color.has(i)) return color.get(i) === c;
        color.set(i, c);
        for (const nei of (arr[i] || [])) {
            if (!dfs(nei, c ? 0 : 1)) return false;        
        }
        return true;
    }
    for (let i = 1; i <= n; i++) {
        if (!color.has(i) && !dfs(i, 0)) {
            return false;
        }
    }
    return true;
};

复杂度分析

---

时间复杂度：O(n + e)，其中E是dislikes的长度。

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

[lizzy-123]

思路

1. 看解析使用的是染色体+深度遍历，但是不太理解 代码

   class Solution {
   public:
   bool paint(int x, int c, vector<vector<int>>& edges, vector<int>& colors) {
       if (colors[x] == c) return true;
       else if (colors[x] != 0 && colors[x] != c) return false;
       colors[x] = c;
       int reversed = (c == 1 ? 2 : 1);
       for (auto& e : edges[x]) {
           if (!paint(e, reversed, edges, colors)) {
               colors[x] = 0;
               return false;
           }
       }
       return true;
   }
   bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
       vector<vector<int>> edges(N);
       for (auto e : dislikes) {
           edges[e[0] - 1].push_back(e[1] - 1);
       }
       vector<int> colors(N, 0);
       for (int i = 0; i < N; ++i) {
           if (!paint(i, 1, edges, colors) && !paint(i, 2, edges, colors)) {
               return false;
           }
       }
       return true;
   }
   };

[L-SUI]

/**

• @param {number[][]} graph

• @return {boolean} */ const isBipartite = (graph) => { const visited = new Array(graph.length); // undefined为未染色，1为蓝色，-1为黄色

  for (let i = 0; i < graph.length; i++) { // 遍历每个顶点 if (visited[i]) continue; // 已经染过色的，跳过 const queue = [i]; // 队列初始推入顶点 i visited[i] = 1; // 染为蓝色

  while (queue.length) {       // 遍历顶点 i 所有相邻的顶点
      const cur = queue.shift();           // 考察出列的顶点
      const curColor = visited[cur];       // 出列顶点的颜色
      const neighborColor = -curColor;     // 它的相邻顶点应该有的颜色
  
      for (let i = 0; i < graph[cur].length; i++) {      // 给他们都上色
          const neighbor = graph[cur][i];
          if (visited[neighbor] == undefined) {          // 还没上色
              visited[neighbor] = neighborColor;         // 上色
              queue.push(neighbor);                      // 并推入队列
          } else if (visited[neighbor] != neighborColor) { // 上了不对的颜色
              return false;
          }
      }
  }

  } return true; // 遍历完所有顶点，没有发现哪里不对 };

[guangshisong]

思路

代码的搬运工

代码

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)

[Lydia61]

可能的二分法

思路

DFS：为题目的dislike关系建图，dislike[i] = [a , b] 代表 a b 之间有一条邻接的边。

代码

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

        def dfs(person, team):
            if teams[person] == -team: return False
            if teams[person] == team: return True
            teams[person] = team
            for next_person in graph[person]:
                if not dfs(next_person, -team):
                    return False
            return True

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

复杂度分析

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

[joeytor]

思路

先建立图, 每个节点用一个 list 包含跟他相连接的其他节点

利用一个 color 数组来记录现在的 分组情况, 0 是 未分组, 1 是 第一组, 2 是 第二组

遍历所有节点, 如果 这个节点未分组 (color == 0) 那么 dfs(i, 1) 给这个节点分成第一组, 如果返回 False,说明有 conflict, 那么返回 False

dfs 时, 先给这个节点 分成 给定的组

​ 然后遍历这个节点的 neighbor

​ 如果跟这个节点同一个颜色, 说明有 conflict, 返回 False

​ 如果 是 0, 那么代表未分组, 所以 dfs(i, -c), 染色成相反的颜色, 如果返回 False, 那么就 return False

​ 如果所有 neighbor 都可以被分组, 返回 True

如果所有节点都可以被分组, 那么就返回 True

代码

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

        # build graph
        graph = collections.defaultdict(list)

        for i, j in dislikes:
            graph[i-1].append(j-1)
            graph[j-1].append(i-1)

        color = [0 for _ in range(n)] # 0 for not grouped, 1 for group 1, -1 for group 2

        def dfs(index, c):
            color[index] = c
            for i in graph[index]:
                if color[i] == 0 and not dfs(i, -c):
                    return False
                if color[i] == c:
                    return False
            return True

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

复杂度

时间复杂度: O(V+E) 因为 colors 是 0 才会进入 dfs, 而且 dfs 中肯定会被染色并且不会撤销染色, 所以每个点和边都最多处理一次, 所以复杂度 是 O(V+E)

空间复杂度: O(V+E) 图的存储用了 O(E) 的复杂度, color 数组是 O(V) 的复杂度, 所以复杂度是 O(V+E)

[iambigchen]

思路

建图存dislikes关系， 遍历每个人，然后进行染色

代码

var possibleBipartition = function(n, dislikes) {
    const graph = new Array(n).fill(0).map(() => new Array());

    for(const [a , b] of dislikes) {
        graph[a - 1].push(b - 1);
        graph[b - 1].push(a - 1);
    }
    const visit = new Array(n).fill(0);
    for(let i = 0 ; i < n ; ++i ) {
        if(!visit[i] && !dfs(i  , 1)) {
            return false;
        }
    }
    return true;

    function dfs (i , color) {
        visit[i] = color;
        for(const adj of graph[i]) {
            if(!visit[adj]) {
                if(!dfs(adj , -color)) return false;
            }else if(color === visit[adj]){
                return false;
            }
        }
        return true;
    }
};

复杂度

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

[july-aha]

占占占
class Solution {
    List<List<Integer>> list=new LinkedList<>();
    int[] color;
    public boolean dfs(int cur,int colors){
        color[cur]=colors;
        for(int i=0;i<list.get(cur).size();i++){
            int j=list.get(cur).get(i);
            if(color[j]==colors) return false;
            if(color[j]==0&&!dfs(j,-colors)) return false;
        }
        return true;
    }
    public boolean possibleBipartition(int N, int[][] dislikes) {
        color=new int[N];
        for(int i=0;i<N;i++){
            list.add(new LinkedList<>());
        }
        for(int i=0;i<dislikes.length;i++){
            list.get(dislikes[i][0]-1).add(dislikes[i][1]-1);
            list.get(dislikes[i][1]-1).add(dislikes[i][0]-1);
        }
        for(int i=0;i<N;i++)
            if(color[i]==0&&!dfs(i,1))
                return false;
        return true;
    }

}

[AnhTom2000]

思路

代码：Java

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;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;node++){ // 对该组n人遍历
         if(!color.containsKey(node)){ // 还未上色
            boolean ok = dfs(node , 0); // 从node开始深度遍历
            if(!ok) return false;
         }
      }
      return true;
    }
    public boolean dfs(int node , int c){
      // 从possibleBipartition调用时node是未上色的
      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+e)，e为dislike长度

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

标签

图,dfs