二分图

# 概念

二分图：所有边的两个顶点刚好分别在两个集合中，且这两个集合内部没有边连接

完全二分图：集合中任意一个点都与另一个集合中的所有点都连通

# 题目

# LC 0785. 判断二分图

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

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        // graph 是一个邻接矩阵
        // 0 没染色，1 白色，-1 黑色
        int n = graph.size();
        vector<int> c(n, 0);  // 点的颜色
        for(int i = 0; i < (int)graph.size(); i++){
            if(c[i] == 0){
                if(!dfs(i, 1, graph, c)) return false;
            }
        }
        return true;
    }

    bool dfs(int i, int pre, vector<vector<int>>&graph, vector<int>&c){
        // i 表示现在的点，pre 表示上一个颜色
        if(c[i]) return c[i] == -pre;

        c[i] = -pre;
        for(auto t: graph[i]){
            if(!dfs(t, -pre, graph, c)) return false;
        }
        return true;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 参考链接

图论基础 (opens new window)

编辑

#图论

上次更新: 2025/05/21, 06:42:57

← 最小生成树 KMP算法→