二分图问题-染色法

24 Aug 2024 in Algorithm Pageviews

solve actually problem!

二分图(Bipartite graph)：节点由两个集合组成，且两个集合内部没有边的图，是一类特殊的图，又称为二部图、偶图、双分图。二分图的顶点可以分为两个互斥的独立集合 U 和 V 的图。

具体形式如下图所示：

从一个题目学习如何判定二分图：

给定一个 n 个顶点 m 条边的无向图，可能存在重边和自环。请判断这个图是否是二分图。

输入格式：

第一行包含 n 和 m, 分别表示 n 个顶点 m 条边。

接下来m行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。

输出格式：

如果给定图是二分图，则输出Yes，否则输出No。

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 100010;
constexpr int M = 200010;
vector<int> h(N, -1);
vector<int> e(M);
vector<int> ne(M);
vector<int> color(N);
int idx = 0;

class Solution {
public:
    void Add(int k, int b)
    {
        e[idx] = b;
        ne[idx] = h[k];
        h[k] = idx++;
    }
    
    bool dfs(int u, int c)
    {
        color[u] = c;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (color[j] == 0) {
                if (!dfs(j, 3 - c)) { // 1->2, 2->1
                    return false;
                }
            }
            if (color[j] == c) {
                return false;
            }
        }
        return true;
    }
};

int main()
{
    Solution sol;
    int n = 0;
    int m = 0;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u = 0;
        int v = 0;
        cin >> u >> v;
        sol.Add(u, v);
        sol.Add(v, u);
    }
    
    bool flag = true;
    for (int i = 1; i <= n; i++) {
        if (color[i] != 0) {
            continue;
        }

        if (!sol.dfs(i, 1)) {
            flag = false;
            break;
        }
    }
    flag ? cout << "Yes" : cout << "No";
    return 0;
}

LeetCode上有一个类似的问题

存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：

• 不存在自环（graph[u] 不包含 u）。
• 不存在平行边（graph[u] 不包含重复值）。
• 如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图）
• 这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。

如果图是二分图，返回 true ；否则，返回 false 。

代码实现：

class Solution {
public:
    bool dfs(const vector<vector<int>>& graph, vector<int> &color, int u, int c)
    {
        color[u] = c;
        for (const auto &j : graph[u]) {
            if ((color[j] == 0) && !dfs(graph, color, j, 3 - c)) {
                return false;
            }
            if (color[j] == c) {
                return false;
            }
        }
        return true;
    }

    bool isBipartite(vector<vector<int>>& graph)
    {
        int N = graph.size();
        vector<int> color(N);
        for (auto i = 0; i < N; i++) {
            if ((color[i] == 0) && !dfs(graph, color, i, 1)) {
                return false;
            }
        }
        return true;
    }
};