Shortest Path SCC

components/shortest_path_scc.hpp · GitHub で見る

共通ページ

負辺最短路で使う、始点から到達可能な部分の強連結成分分解です。DirectedCSR<W> または (行き先,重み) の隣接リストを受け取ります。重みは読みません。再帰を使わない Tarjan 法です。

操作・メンバー	内容・返り値	計算量
negative_path_detail::reachable_components(g,s)	到達可能な部分を分解し、Components を返す	\(O(n+m)\)
result.id[v]	成分番号。到達不能は -1。異なる成分への辺は番号が大きい方から小さい方へ向かう	\(O(1)\)
result.vertices	成分ごとに並べた到達可能頂点	参照 \(O(1)\)
result.offset[c] / result.offset[c+1]	vertices 内で成分 c の頂点が入る半開区間の両端	\(O(1)\)

offset.size()-1 が成分数です。成分間を辺の向きに沿って処理する場合は、番号の大きい方から処理します。頂点数を \(n\)、辺数を \(m\) として、時間は \(O(n+m)\)、追加空間は \(O(n)\) です。

検証コード

• test/bellman_ford.test.cpp
• test/bellman_ford_path.test.cpp
• test/difference_constraints.test.cpp

コード

#ifndef SHORTEST_PATH_SCC_HPP
#define SHORTEST_PATH_SCC_HPP

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <limits>
#include <vector>

namespace negative_path_detail {
struct Components {
	std::vector<int> id, vertices;
	std::vector<std::size_t> offset{0};
};
template<class Graph>
Components reachable_components(const Graph &g, int source) {
	assert(std::size_t(g.size()) <= std::size_t(std::numeric_limits<int>::max()));
	int n = static_cast<int>(g.size());
	assert(0 <= source && source < n);
	Components result;
	result.id.assign(n, -1);
	std::vector<int> index(n, -1), low(n), pending;
	struct Frame { int vertex; std::size_t next; };
	std::vector<Frame> stack;
	int clock = 0, count = 0;
	auto enter = [&](int v) {
		index[v] = low[v] = clock++;
		pending.push_back(v);
		stack.push_back({v, 0});
	};
	enter(source);
	while (!stack.empty()) {
		int v = stack.back().vertex;
		if (stack.back().next < g[v].size()) {
			int to = g[v][stack.back().next++].first;
			assert(0 <= to && to < n);
			if (index[to] == -1) enter(to);
			else if (result.id[to] == -1) low[v] = std::min(low[v], index[to]);
		} else {
			stack.pop_back();
			if (low[v] == index[v]) {
				int u;
				do {
					u = pending.back();
					pending.pop_back();
					result.id[u] = count;
					result.vertices.push_back(u);
				} while (u != v);
				++count;
				result.offset.push_back(result.vertices.size());
			}
			if (!stack.empty()) {
				int parent = stack.back().vertex;
				low[parent] = std::min(low[parent], low[v]);
			}
		}
	}
	return result;
}
}

#endif

Back to top page