topological_sort (トポロジカルソート)
(src/graph/simple/topological_sort.hpp)

• View this file on GitHub
• Last update: 2023-02-27 01:26:01+09:00
• Include: #include "src/graph/simple/topological_sort.hpp"

概要

入力で与えられた有向グラフ $G(V, E)$ をトポロジカルソート します。

機能

コンストラクタ

(1) zawa::topological_sort(const std::vector<std::vector<int>>& _G)
(2) zawa::topological_sort<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

に対して read_graph(n, m, false) とすることで対応する _G を作成することが可能です。しかし、第三引数をデフォルト引数の true から falseに変えるという注意が必要なため、自身で 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

[]

int operator[](int i)

トポロジカルソート列 $A$ について $A_i$ を返します。

制約

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

$G$ はトポロジカルソートが可能なグラフである

• 後述のメンバ関数、ok等で確認できます

メンバ

ok

inline bool ok() const 

トポロジカルソート列が構築できたかの是非を返します。

トポロジカルソート列が構築できる時、 $G$ は DAG であると言えます。(美味い性質やDAGであることを利用した典型テクがいくつかある）

計算量 :

$O(1)$

get

inline std::vector<int> get() const

トポロジカルソート列を返します。

制約

$G$ はトポロジカルソートが可能なグラフである

• ok等で確認できます

計算量

$O(\mid V\mid)$

unique

bool unique() const

$G$ のトポロジカルソートが一意に定まるかを判定します。(そもそもトポロジカルソート列が構築できない場合、falseが返ります)

計算量

$O(\mid V\mid + \mid E\mid)$

Verified with

• test/ABC285-D.test.cpp
• test/AOJ0519.test.cpp
• test/simple-topological_sort.test.cpp

Code

#pragma once

#include <vector>
#include <stack>

namespace zawa {

class topological_sort {
private:
	std::vector<std::vector<int>> G;
	std::vector<int> Ord;
	bool is_dag;

	bool build() {
		std::vector<int> In(G.size(), 0);
		for (std::size_t i = 0 ; i < G.size() ; i++) {
			for (const auto& v : G[i]) {
				In[v]++;
			}
		}
		std::stack<int> S;
		for (std::size_t i = 0 ; i < G.size() ; i++) {
			if (!In[i]) {
				S.push(i);
			}
		}
		while (S.size()) {
			int v = S.top();
			S.pop();
			Ord.push_back(v);
			for (auto x : G[v]) {
				In[x]--;
				if (!In[x]) {
					S.push(x);
				}
			}
		}
		return Ord.size() == G.size();
	}

public:
	topological_sort(const std::vector<std::vector<int>>& _G) : G(_G), is_dag(build()) {}	

	template <class cost_type>
	topological_sort(const std::vector<std::vector<std::pair<int, cost_type>>>& _G) :  G(_G.size()) {
		for (std::size_t i = 0 ; i < _G.size() ; i++) {
			for (auto [v, _] : _G[i]) {
				G[i].push_back(v);
			}
		}	
		is_dag = build();
	}

	inline bool ok() const {
		return is_dag;
	}

	int operator[](int i) {
		return Ord[i];
	}

	inline std::vector<int> get() const {
		return Ord;
	}

	bool unique() const {
		if (!is_dag) {
			return false;
		}
		bool res = true;
		for (std::size_t i = 0 ; i + 1 < G.size() ; i++) {
			bool ok = false;
			for (const auto& v : G[Ord[i]]) {
				ok |= v == Ord[i + 1];
			}
			res &= ok;
		}
		return res;
	}
};

} // namespace zawa

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

#include <vector>
#include <stack>

namespace zawa {

class topological_sort {
private:
	std::vector<std::vector<int>> G;
	std::vector<int> Ord;
	bool is_dag;

	bool build() {
		std::vector<int> In(G.size(), 0);
		for (std::size_t i = 0 ; i < G.size() ; i++) {
			for (const auto& v : G[i]) {
				In[v]++;
			}
		}
		std::stack<int> S;
		for (std::size_t i = 0 ; i < G.size() ; i++) {
			if (!In[i]) {
				S.push(i);
			}
		}
		while (S.size()) {
			int v = S.top();
			S.pop();
			Ord.push_back(v);
			for (auto x : G[v]) {
				In[x]--;
				if (!In[x]) {
					S.push(x);
				}
			}
		}
		return Ord.size() == G.size();
	}

public:
	topological_sort(const std::vector<std::vector<int>>& _G) : G(_G), is_dag(build()) {}	

	template <class cost_type>
	topological_sort(const std::vector<std::vector<std::pair<int, cost_type>>>& _G) :  G(_G.size()) {
		for (std::size_t i = 0 ; i < _G.size() ; i++) {
			for (auto [v, _] : _G[i]) {
				G[i].push_back(v);
			}
		}	
		is_dag = build();
	}

	inline bool ok() const {
		return is_dag;
	}

	int operator[](int i) {
		return Ord[i];
	}

	inline std::vector<int> get() const {
		return Ord;
	}

	bool unique() const {
		if (!is_dag) {
			return false;
		}
		bool res = true;
		for (std::size_t i = 0 ; i + 1 < G.size() ; i++) {
			bool ok = false;
			for (const auto& v : G[Ord[i]]) {
				ok |= v == Ord[i + 1];
			}
			res &= ok;
		}
		return res;
	}
};

} // namespace zawa

Back to top page