Bipartite Graph Recognition
(library/graph/bipartite_graph_recognition.hpp)

• View this file on GitHub
• Last update: 2022-03-17 16:17:30+09:00
• Include: #include "library/graph/bipartite_graph_recognition.hpp"

Bipartite Graph Recognition

Verified with

• test/src/graph/dulmage_mendelsohn_decomposition/abc223_g.test.cpp

Code

#ifndef SUISEN_BIPARTITE_GRAPH_RECOGNITION
#define SUISEN_BIPARTITE_GRAPH_RECOGNITION

#include <deque>
#include <optional>
#include <vector>

namespace suisen {
    static std::optional<std::vector<int>> bipartite_coloring(const std::vector<std::vector<int>>& g, int col0 = 0, int col1 = 1) {
        const int n = g.size();
        int uncolored = 2;
        while (uncolored == col0 or uncolored == col1) ++uncolored;
        std::vector<int> color(n, uncolored);
        for (int i = 0; i < n; ++i) {
            if (color[i] != uncolored) continue;
            color[i] = col0;
            std::deque<int> dq { i };
            while (dq.size()) {
                int u = dq.front();
                dq.pop_front();
                for (int v : g[u]) {
                    if (color[v] == uncolored) {
                        dq.push_back(v);
                        color[v] = color[u] ^ col0 ^ col1;
                    } else if (color[v] == color[u]) {
                        return std::nullopt;
                    }
                }
            }
        }
        return color;
    }
} // namespace suisen


#endif // SUISEN_BIPARTITE_GRAPH_RECOGNITION

#line 1 "library/graph/bipartite_graph_recognition.hpp"



#include <deque>
#include <optional>
#include <vector>

namespace suisen {
    static std::optional<std::vector<int>> bipartite_coloring(const std::vector<std::vector<int>>& g, int col0 = 0, int col1 = 1) {
        const int n = g.size();
        int uncolored = 2;
        while (uncolored == col0 or uncolored == col1) ++uncolored;
        std::vector<int> color(n, uncolored);
        for (int i = 0; i < n; ++i) {
            if (color[i] != uncolored) continue;
            color[i] = col0;
            std::deque<int> dq { i };
            while (dq.size()) {
                int u = dq.front();
                dq.pop_front();
                for (int v : g[u]) {
                    if (color[v] == uncolored) {
                        dq.push_back(v);
                        color[v] = color[u] ^ col0 ^ col1;
                    } else if (color[v] == color[u]) {
                        return std::nullopt;
                    }
                }
            }
        }
        return color;
    }
} // namespace suisen

Back to top page