bipartiteJudge (二部グラフ判定)
(src/graph/simple/bipartiteJudge.hpp)

• View this file on GitHub
• Last update: 2023-03-04 20:28:25+09:00
• Include: #include "src/graph/simple/bipartiteJudge.hpp"

概要

グラフ $G(V, E)$ が二部グラフであるかを判定します。

二部グラフとは、グラフの各頂点を二色で塗り分ける方法であって、どの辺で隣接する頂点の対も同じ色で塗られないものが存在するものを指します。

機能

コンストラクタ

(1) zawa::bipartiteJudge(const std::vector<std::vector<int>>& G)
(2) zawa::bipartiteJudge<cost_type>(const std::vector<std::vector<std::pair<int, cost_type>>>& G)

(1)

G $G$ の隣接リスト表現です。正確には以下の条件を満たす std::vector<std::vector<int>> です

頂点 $u$ から頂点 $v$ への有向辺が存在する時、その時に限り G[u][i] = v なる $i$ が存在する

AtCoder等のグラフの一般的な入力形式

N M

u_1 v_1

...

u_M v_M

に対して zawa::read_graph(n, m) とすることで対応する G を作成することが可能です。

(2)

辺重みがある $G$ に対してはこちらを利用します。

頂点 $u$ から頂点 $v$ へのコストcの有向辺が存在する時、その時に限り G[u][i] = std::pair<int, cost_type>(v, c) なる $i$ が存在する

ことがGの条件です

計算量: (1)(2)共に $O(\mid V\mid + \mid E\mid)$

operator

[]

inline bool operator[](int i)

$G$ が二部グラフであった場合、このclassはある条件を満たす二色の塗り分けを行っている。このoperatorはそのような塗り分け方を一つ行ったときの頂点 $i$ の色を返す。

• 条件を満たす塗り分け方が複数存在する場合、そのどれが採用されているかは不明

制約

$0\ \le\ i\ <\ \mid V\mid$

$G$ が二部グラフである

• 後述のメンバ関数、okで二部グラフかどうかを判定できます。

計算量

$O(1)$

メンバ関数

ok

inline bool ok() const

$G$ が二部グラフであるかを判定します。

計算量

$O(1)$

Verified with

• test/ABC199-D.test.cpp
• test/ABC282-D.test.cpp
• test/simple-bipartite-judge1.test.cpp

Code

#pragma once

#include <vector>
#include <stack>
#include <utility>

namespace zawa {

class bipartiteJudge {
private:
	std::vector<bool> colors;
	bool isBipartiteGraph;

	void build(const std::vector<std::vector<int>>& G) {
		if (G.empty()) {
			return;
		}
		std::stack<std::pair<int, bool>> S;
		std::vector<bool> used(G.size(), false);
		for (int i = 0 ; i < (int)G.size() ; i++) {
			if (!used[i]) {
				S.emplace(i, true);
				used[i] = true;
				colors[i] = true;
				while (S.size()) {
					auto [v, col] = S.top();
					S.pop();
					for (const auto& x : G[v]) {
						if (used[x]) {
							isBipartiteGraph &= colors[x] != col;
						}
						else {
							used[x] = true;
							colors[x] = !col;
							S.emplace(x, !col);
						}
					}
				}
			}
		}
	}

public:
	
	bipartiteJudge(const std::vector<std::vector<int>>& G) : colors(G.size()), isBipartiteGraph(true) {
		build(G);
	}

	template <class cost_type>
	bipartiteJudge(const std::vector<std::vector<std::pair<int, cost_type>>>& G) : colors(G.size()), isBipartiteGraph(true) {
		std::vector tmpG(G.size(), std::vector(0, 0));
		for (std::size_t i = 0 ; i < G.size() ; i++) {
			for (const auto& [x, _] : G[i]) {
				tmpG[i].push_back(x);
			}
		}
		build(tmpG);
	}

	inline const bool ok() const {
		return isBipartiteGraph;
	}

	inline bool operator[](int i) const {
		return colors[i];
	}
};

} // namespace zawa

#line 2 "src/graph/simple/bipartiteJudge.hpp"

#include <vector>
#include <stack>
#include <utility>

namespace zawa {

class bipartiteJudge {
private:
	std::vector<bool> colors;
	bool isBipartiteGraph;

	void build(const std::vector<std::vector<int>>& G) {
		if (G.empty()) {
			return;
		}
		std::stack<std::pair<int, bool>> S;
		std::vector<bool> used(G.size(), false);
		for (int i = 0 ; i < (int)G.size() ; i++) {
			if (!used[i]) {
				S.emplace(i, true);
				used[i] = true;
				colors[i] = true;
				while (S.size()) {
					auto [v, col] = S.top();
					S.pop();
					for (const auto& x : G[v]) {
						if (used[x]) {
							isBipartiteGraph &= colors[x] != col;
						}
						else {
							used[x] = true;
							colors[x] = !col;
							S.emplace(x, !col);
						}
					}
				}
			}
		}
	}

public:
	
	bipartiteJudge(const std::vector<std::vector<int>>& G) : colors(G.size()), isBipartiteGraph(true) {
		build(G);
	}

	template <class cost_type>
	bipartiteJudge(const std::vector<std::vector<std::pair<int, cost_type>>>& G) : colors(G.size()), isBipartiteGraph(true) {
		std::vector tmpG(G.size(), std::vector(0, 0));
		for (std::size_t i = 0 ; i < G.size() ; i++) {
			for (const auto& [x, _] : G[i]) {
				tmpG[i].push_back(x);
			}
		}
		build(tmpG);
	}

	inline const bool ok() const {
		return isBipartiteGraph;
	}

	inline bool operator[](int i) const {
		return colors[i];
	}
};

} // namespace zawa

Back to top page