LeetCode 886. 可能的二分法

Categories:

题目描述
思路分析
1. 解法一：二分图判定（推荐）
相似题目

题目描述

✅ 886. 可能的二分法

思路分析

解法一：二分图判定（推荐）

核心思路：

将人视为图的节点，互相讨厌的人连一条无向边。

使用 BFS/DFS 进行二染色，若出现相邻节点同色则不可二分。

图可能不连通，需要遍历所有节点。

复杂度分析：

时间复杂度：O(V + E)，其中 V 表示人数，E 表示讨厌关系数。

空间复杂度：O(V + E)，用于邻接表与队列。

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

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

        int[] color = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            if (color[i] != 0) {
                continue;
            }
            Deque<Integer> queue = new ArrayDeque<>();
            queue.offer(i);
            color[i] = 1;

            while (!queue.isEmpty()) {
                int cur = queue.poll();
                for (int next : graph[cur]) {
                    if (color[next] == 0) {
                        color[next] = -color[cur];
                        queue.offer(next);
                    } else if (color[next] == color[cur]) {
                        return false;
                    }
                }
            }
        }

        return true;
    }
}

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

	color := make([]int, n+1)
	for i := 1; i <= n; i++ {
		if color[i] != 0 {
			continue
		}
		queue := make([]int, 0)
		queue = append(queue, i)
		color[i] = 1

		for len(queue) > 0 {
			cur := queue[0]
			queue = queue[1:]
			for _, next := range graph[cur] {
				if color[next] == 0 {
					color[next] = -color[cur]
					queue = append(queue, next)
				} else if color[next] == color[cur] {
					return false
				}
			}
		}
	}

	return true
}

相似题目

题目	难度	考察点
785. 判断二分图	中等	二分图
1042. 不邻接植花	中等	图染色
547. 省份数量	中等	并查集
1319. 连通网络的操作次数	中等	并查集
841. 钥匙和房间	中等	图遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/24649919