LeetCode 785. 判断二分图

Categories:

题目描述
思路分析
1. 解法一：染色 + BFS（推荐）
相似题目

题目描述

✅ 785. 判断二分图

思路分析

解法一：染色 + BFS（推荐）

核心思路：

用颜色数组 color 表示节点所属集合，未访问为 0。

对每个连通分量进行 BFS，尝试二染色。

若出现相邻节点同色，则不是二分图。

复杂度分析：

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

空间复杂度：O(V)。

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];

        for (int i = 0; i < n; i++) {
            if (color[i] != 0) {
                continue;
            }
            Deque<Integer> queue = new ArrayDeque<>();
            queue.add(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.add(next);
                    } else if (color[next] == color[cur]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

func isBipartite(graph [][]int) bool {
	n := len(graph)
	color := make([]int, n)

	for i := 0; i < n; i++ {
		if color[i] != 0 {
			continue
		}
		queue := []int{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. 判断二分图	中等	图、染色
886. 可能的二分法	中等	图、染色
210. 课程表 II	中等	图、拓扑
207. 课程表	中等	图、拓扑
133. 克隆图	中等	图、DFS/BFS
841. 钥匙和房间	中等	图、DFS/BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/18421836