Check whether a given graph is bipartite (tools/is_bipartite.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-03-24 16:56:26+09:00
• Include: #include "tools/is_bipartite.hpp"

It checks whether a given undirected graph is bipartite.

License

• CC0

Author

• anqooqie

Constructor

is_bipartite graph(std::size_t n);

It creates an undirected graph with $n$ vertices and $0$ edges.

Constraints

• None

Time Complexity

• $O(n)$

size

std::size_t graph.size();

It returns $n$.

Constraints

• None

Time Complexity

• $O(1)$

add_edge

std::size_t graph.add_edge(std::size_t u, std::size_t v);

It adds an undirected edge between $u$ and $v$. It returns an integer $k$ such that this is the $k$-th ($0$ indexed) edge that is added.

Constraints

• $0 \leq u < n$
• $0 \leq v < n$

Time Complexity

• $O(1)$ amortized

get_edge

struct edge {
  std::size_t id;
  std::size_t from;
  std::size_t to;
};
const edge& graph.get_edge(std::size_t k);

It returns the $k$-th ($0$ indexed) edge.

Constraints

• $0 \leq k < |E|$ where $|E|$ is the number of edges

Time Complexity

• $O(1)$

edges

const std::vector<edge>& graph.edges();

It returns all the edges in the graph. The edges are ordered in the same order as added by add_edge.

Constraints

• None

Time Complexity

• $O(1)$

query

bool graph.query();

If the graph is bipartite, it returns true. Otherwise, it returns false.

Constraints

• None

Time Complexity

• $O(n + |E|)$ where $|E|$ is the number of edges

Verified with

• tests/is_bipartite.test.cpp

Code

#ifndef TOOLS_IS_BIPARTITE_HPP
#define TOOLS_IS_BIPARTITE_HPP

#include <cstddef>
#include <vector>
#include <cassert>
#include <tuple>
#include <algorithm>
#include <string>
#include <queue>

namespace tools {

  class is_bipartite {
  public:
    struct edge {
      ::std::size_t id;
      ::std::size_t from;
      ::std::size_t to;
    };

  private:
    ::std::vector<edge> m_edges;
    ::std::vector<::std::vector<::std::size_t>> m_graph;

  public:
    is_bipartite() = default;
    explicit is_bipartite(const ::std::size_t n) : m_graph(n) {
    }

    ::std::size_t size() const {
      return this->m_graph.size();
    }

    ::std::size_t add_edge(::std::size_t u, ::std::size_t v) {
      assert(u < this->size());
      assert(v < this->size());
      ::std::tie(u, v) = ::std::minmax({u, v});
      this->m_edges.push_back(edge{this->m_edges.size(), u, v});
      this->m_graph[u].push_back(this->m_edges.size() - 1);
      this->m_graph[v].push_back(this->m_edges.size() - 1);
      return this->m_edges.size() - 1;
    }

    const edge& get_edge(const ::std::size_t k) const {
      assert(k < this->m_edges.size());
      return this->m_edges[k];
    }

    const ::std::vector<edge>& edges() const {
      return this->m_edges;
    }

    bool query() const {
      ::std::string belongs(this->size(), '?');
      for (::std::size_t root = 0; root < this->size(); ++root) {
        if (belongs[root] == '?') {
          ::std::queue<::std::size_t> queue({root});
          belongs[root] = '0';
          while (!queue.empty()) {
            const auto here = queue.front();
            queue.pop();
            for (const auto edge_id : this->m_graph[here]) {
              const auto& edge = this->m_edges[edge_id];
              const auto next = edge.from ^ edge.to ^ here;
              if (belongs[next] == '?') {
                belongs[next] = ((belongs[here] - '0') ^ 1) + '0';
                queue.push(next);
              } else {
                if (belongs[here] == belongs[next]) {
                  return false;
                }
              }
            }
          }
        }
      }

      return true;
    }
  };
}

#endif

#line 1 "tools/is_bipartite.hpp"



#include <cstddef>
#include <vector>
#include <cassert>
#include <tuple>
#include <algorithm>
#include <string>
#include <queue>

namespace tools {

  class is_bipartite {
  public:
    struct edge {
      ::std::size_t id;
      ::std::size_t from;
      ::std::size_t to;
    };

  private:
    ::std::vector<edge> m_edges;
    ::std::vector<::std::vector<::std::size_t>> m_graph;

  public:
    is_bipartite() = default;
    explicit is_bipartite(const ::std::size_t n) : m_graph(n) {
    }

    ::std::size_t size() const {
      return this->m_graph.size();
    }

    ::std::size_t add_edge(::std::size_t u, ::std::size_t v) {
      assert(u < this->size());
      assert(v < this->size());
      ::std::tie(u, v) = ::std::minmax({u, v});
      this->m_edges.push_back(edge{this->m_edges.size(), u, v});
      this->m_graph[u].push_back(this->m_edges.size() - 1);
      this->m_graph[v].push_back(this->m_edges.size() - 1);
      return this->m_edges.size() - 1;
    }

    const edge& get_edge(const ::std::size_t k) const {
      assert(k < this->m_edges.size());
      return this->m_edges[k];
    }

    const ::std::vector<edge>& edges() const {
      return this->m_edges;
    }

    bool query() const {
      ::std::string belongs(this->size(), '?');
      for (::std::size_t root = 0; root < this->size(); ++root) {
        if (belongs[root] == '?') {
          ::std::queue<::std::size_t> queue({root});
          belongs[root] = '0';
          while (!queue.empty()) {
            const auto here = queue.front();
            queue.pop();
            for (const auto edge_id : this->m_graph[here]) {
              const auto& edge = this->m_edges[edge_id];
              const auto next = edge.from ^ edge.to ^ here;
              if (belongs[next] == '?') {
                belongs[next] = ((belongs[here] - '0') ^ 1) + '0';
                queue.push(next);
              } else {
                if (belongs[here] == belongs[next]) {
                  return false;
                }
              }
            }
          }
        }
      }

      return true;
    }
  };
}

Back to top page