reachability (到達可能性)
(src/graph/simple/reachability.hpp)

• View this file on GitHub
• Last update: 2023-02-13 09:43:35+09:00
• Include: #include "src/graph/simple/reachability.hpp"

概要

有向グラフ $G(V, E)$ 上での頂点 $\text{from}$ から頂点 $\text{to}$ へ到達可能かを判定します。

DFSによる愚直な実装です。

無向グラフに関しては連結成分分解 (zawa::connected_components::same) で全く同じことができる上、クエリ回答が可能です。

機能

関数

bool zawa::reachability(std::vector<std::vector<int>>& G, int from, int to)

• G: $G$ の隣接リスト表現
  • G: $u$ から $v$ への有向辺が存在する時、またその時に限り G[u][i] = vなるiが存在するようにする
  • AtCoderなどではzawa::read_graph(n, m)とすることで入力から対応するGを作成することが可能です。 ( $n\ =\ \mid V\mid, m\ =\ \mid E\mid$ )
• from: $\text{from}$
• to: $\text{to}$
• 返り値: 到達可能ならtrue、そうでないならfalse
• 計算量 : $O(\mid V\mid + \mid E\mid)$

bool zawa::reachability(std::vector<std::vector<std::pair<int, cost_type>>>& G, int from, int to)

• $E$ に重みがついている場合はこちらをお使いください
  • 最短経路等は求めません。(ダイクストラとか書いて)
• 未テスト

余談

到達可能性問題がクエリとしてたくさん飛んでくる場合

• scc + bitset高速化
• 平面グラフならもっと早いのがあるっぽい？

Verified with

• test/ABC289-D.test.cpp

Code

#pragma once

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

namespace zawa {

bool reachability(const std::vector<std::vector<int>>& G, int from, int to) {
	std::stack<int> stk;
	std::vector visited(G.size(), false);
	visited[from] = true;
	stk.emplace(from);
	while (stk.size()) {
		int v = stk.top();
		stk.pop();
		if (v == to) {
			return true;
		}
		for (const auto& x : G[v]) {
			if (!visited[x]) {
				visited[x] = true;
				stk.emplace(x);
			}
		}
	}
	return false;
}

template <class cost_type>
bool reachability(const std::vector<std::vector<std::pair<int, cost_type>>>& G, int from, int to) {
	std::vector tmp(G.size(), std::vector(0, 0));
	for (int i = 0 ; i < (int)G.size() ; i++) {
		for (auto [x, _] : G[i]) {
			tmp[i].emplace(x);
		}
	}
	return reachability(tmp, from, to);
}

} // namespace zawa

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

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

namespace zawa {

bool reachability(const std::vector<std::vector<int>>& G, int from, int to) {
	std::stack<int> stk;
	std::vector visited(G.size(), false);
	visited[from] = true;
	stk.emplace(from);
	while (stk.size()) {
		int v = stk.top();
		stk.pop();
		if (v == to) {
			return true;
		}
		for (const auto& x : G[v]) {
			if (!visited[x]) {
				visited[x] = true;
				stk.emplace(x);
			}
		}
	}
	return false;
}

template <class cost_type>
bool reachability(const std::vector<std::vector<std::pair<int, cost_type>>>& G, int from, int to) {
	std::vector tmp(G.size(), std::vector(0, 0));
	for (int i = 0 ; i < (int)G.size() ; i++) {
		for (auto [x, _] : G[i]) {
			tmp[i].emplace(x);
		}
	}
	return reachability(tmp, from, to);
}

} // namespace zawa

Back to top page