Topological-Sort(トポロジカルソート) (graph/topological_sort.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2021-03-02 23:16:05+09:00

なにこれ

グラフの隣接リストを元に，各辺について終点より始点が先にくる頂点配列を求める．

関数

• topological(lst)：隣接リスト lst を元に，トポロジカルソートした頂点配列を返す．
• topological(lst, indeg)：隣接リスト lst，頂点の入次数を格納した配列 indeg を元に，トポロジカルソートした頂点配列を返す．

計算量

頂点数を $V$，辺の数を $E$ とする．

• topological(lst)：$O(V+E)$
• topological(lst, indeg)：$O(V+E)$

---

Verified with (AtCoder)

• abc139_e
• nikkei2019_qual_d

Depends on

• 2D-Array( $2$ 次元配列) (structure/2d_array.cpp)

Verified with

• test/aoj_GRL_4_B.cpp
• test/atc_nikkei2019-qual_d.cpp
• test/yuki_0497.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

#include "../structure/2d_array.cpp"

vector<int> topological(v2d<int> &lst, vector<int> &indeg) {
	int V = lst.size(), vtmp = lst.size();
	vector<int> res;

	queue<int> q;
	for(int i = 0; i < V; i++) {
		if(indeg[i] == 0) q.push(i);
	}

	while(!q.empty()) {
		int v = q.front();
		q.pop();

		for(const int nv : lst[v]) {
			indeg[nv]--;
			if(indeg[nv] == 0) q.push(nv);
		}

		res.emplace_back(v);
		vtmp--;
	}

	if(vtmp) return {-1};
	return res;
}

vector<int> topological(v2d<int> &lst) {
	vector<int> indeg(lst.size(), 0);

	for(int i = 0; i < lst.size(); i++)
		for(const int v : lst[i]) indeg[v]++;

	return topological(lst, indeg);
}

#line 2 "graph/topological_sort.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

#line 2 "structure/2d_array.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

template<typename T> struct v2d {
private:
	vector<vector<T>> m;

public:
	v2d() {}
	v2d(int h, int w) : m(h, vector<T>(w)) {}
	v2d(int h, int w, const T &init) : m(h, vector<T>(w, init)) {}
	v2d(const initializer_list<initializer_list<T>> m_init) : m(m_init.begin(), m_init.end()) {}

	void assign(int h, int w) {
		m.assign(h, vector<T>(w));
	}
	void assign(int h, int w, const T init) {
		m.assign(h, vector<T>(w, init));
	}

	inline int size() const {
		return m.size();
	}

	void in() {
		for(vector<T> &v : m)
			for(T &val : v) cin >> val;
	}
	void in(int h, int w) {
		m.resize(h, vector<T>(w));
		in();
	}

	void out() {
		int h = m.size();
		for(vector<T> &v : m) {
			int sz = v.size();
			for(int j = 0; j < sz; j++) {
				cout << v[j] << (j == sz - 1 ? '\n' : ' ');
			}
		}
		cout << flush;
	}

	inline vector<T> &operator[](int idx) {
		assert(0 <= idx && idx < m.size());
		return m[idx];
	}

	bool rangeout(int x, int y) {
		if(x < 0 || y < 0 || x >= size() || y >= m[x].size()) return true;
		return false;
	}
};
#line 10 "graph/topological_sort.cpp"

vector<int> topological(v2d<int> &lst, vector<int> &indeg) {
	int V = lst.size(), vtmp = lst.size();
	vector<int> res;

	queue<int> q;
	for(int i = 0; i < V; i++) {
		if(indeg[i] == 0) q.push(i);
	}

	while(!q.empty()) {
		int v = q.front();
		q.pop();

		for(const int nv : lst[v]) {
			indeg[nv]--;
			if(indeg[nv] == 0) q.push(nv);
		}

		res.emplace_back(v);
		vtmp--;
	}

	if(vtmp) return {-1};
	return res;
}

vector<int> topological(v2d<int> &lst) {
	vector<int> indeg(lst.size(), 0);

	for(int i = 0; i < lst.size(); i++)
		for(const int v : lst[i]) indeg[v]++;

	return topological(lst, indeg);
}

Back to top page