Medium

题目描述

我们想要将一组 n 个人（编号从 1 到 n）分成两个任意大小的组。每个人可能不喜欢其他一些人，他们不应该被分到同一组中。

给定整数 n 和数组 dislikes，其中 dislikes[i] = [ai, bi] 表示编号为 ai 的人不喜欢编号为 bi 的人，如果可以用这种方式将每个人分成两组，则返回 true。

示例 1：

输入：n = 4, dislikes = [[1,2],[1,3],[2,4]]
输出：true
解释：第一组包含 [1,4]，第二组包含 [2,3]。

示例 2：

输入：n = 3, dislikes = [[1,2],[1,3],[2,3]]
输出：false
解释：我们至少需要 3 个组来分隔他们。我们无法将他们分成两组。

提示：

  • 1 <= n <= 2000
  • 0 <= dislikes.length <= 10⁴
  • dislikes[i].length == 2
  • 1 <= ai < bi <= n
  • 所有不喜欢的关系都是唯一的

解题思路

这道题本质上是判断一个无向图是否为二分图的问题。

核心思路：

  1. 将每个人看作图的节点，不喜欢关系看作边
  2. 如果能将所有人分成两组且组内无冲突，等价于图可以二分着色
  3. 二分图的特征是图中不存在奇数长度的环

解法一：DFS染色法（推荐）

  • 使用数组记录每个节点的颜色（0未访问，1红色，-1蓝色）
  • 从每个未访问节点开始DFS，尝试给相邻节点染不同颜色
  • 如果发现相邻节点已经染了相同颜色，说明不是二分图

解法二：BFS染色法

  • 思路类似DFS，但使用队列进行层次遍历
  • 适合处理深度较深的图

解法三：并查集

  • 对于每个节点，将其所有"敌人"归为一类
  • 检查是否存在节点与其敌人在同一集合中

DFS解法最直观且效率较高，是首选方案。

代码实现

class Solution {
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        vector<vector<int>> graph(n + 1);
        for (auto& edge : dislikes) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        
        vector<int> color(n + 1, 0);
        
        for (int i = 1; i <= n; i++) {
            if (color[i] == 0 && !dfs(graph, color, i, 1)) {
                return false;
            }
        }
        return true;
    }
    
private:
    bool dfs(vector<vector<int>>& graph, vector<int>& color, int node, int c) {
        color[node] = c;
        for (int neighbor : graph[node]) {
            if (color[neighbor] == c) return false;
            if (color[neighbor] == 0 && !dfs(graph, color, neighbor, -c)) {
                return false;
            }
        }
        return true;
    }
};

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        graph = [[] for _ in range(n + 1)]
        for a, b in dislikes:
            graph[a].append(b)
            graph[b].append(a)
        
        color = [0] * (n + 1)
        
        def dfs(node, c):
            color[node] = c
            for neighbor in graph[node]:
                if color[neighbor] == c:
                    return False
                if color[neighbor] == 0 and not dfs(neighbor, -c):
                    return False
            return True
        
        for i in range(1, n + 1):
            if color[i] == 0 and not dfs(i, 1):
                return False
        
        return True

public class Solution {
    public bool PossibleBipartition(int n, int[][] dislikes) {
        List<int>[] graph = new List<int>[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var edge in dislikes) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        
        int[] color = new int[n + 1];
        
        for (int i = 1; i <= n; i++) {
            if (color[i] == 0 && !Dfs(graph, color, i, 1)) {
                return false;
            }
        }
        return true;
    }
    
    private bool Dfs(List<int>[] graph, int[] color, int node, int c) {
        color[node] = c;
        foreach (int neighbor in graph[node]) {
            if (color[neighbor] == c) return false;
            if (color[neighbor] == 0 && !Dfs(graph, color, neighbor, -c)) {
                return false;
            }
        }
        return true;
    }
}

var possibleBipartition = function(n, dislikes) {
    const graph = Array.from({ length: n + 1 }, () => []);
    
    for (const [a, b] of dislikes) {
        graph[a].push(b);
        graph[b].push(a);
    }
    
    const color = new Array(n + 1).fill(0);
    
    const dfs = (node, c) => {
        color[node] = c;
        for (const neighbor of graph[node]) {
            if (color[neighbor] === c) return false;
            if (color[neighbor] === 0 && !dfs(neighbor, -c)) return false;
        }
        return true;
    };
    
    for (let i = 1; i <= n; i++) {
        if (color[i] === 0 && !dfs(i, 1)) {
            return false;
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度DFS解法
时间复杂度O(V + E)
空间复杂度O(V + E)

其中 V = n（节点数），E = dislikes.length（边数）。时间复杂度中访问每个节点和边各一次，空间复杂度主要用于存储邻接表和递归栈。