test/simple-topological_sort.test.cpp

• View this file on GitHub
• Last update: 2023-02-27 01:26:01+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://onlinejudge.u-aizu.ac.jp/status/users/zawakasu/submissions/1/GRL_4_B/judge/7516185/C++17

Depends on

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

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../src/graph/simple/topological_sort.hpp"

#include <iostream>
#include <vector>

int main() {
	// int V, E; std::cin >> V >> E;
	// std::vector G(V, std::vector(0, 0));
	// for (int _ = 0 ; _ < E ; _++) {
	// 	int s, t; std::cin >> s >> t;
	// 	G[s].push_back(t);
	// }
	// for (const auto& v : zawa::topological_sort(G).get()) {
	// 	std::cout << v << std::endl;
	// }
	std::cout << "Hello World" << std::endl;
}

/*
 * AOJ GRL_4_B トポロジカルソート
 * https://onlinejudge.u-aizu.ac.jp/status/users/zawakasu/submissions/1/GRL_4_B/judge/7516185/C++17
 */

#line 1 "test/simple-topological_sort.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#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
#line 4 "test/simple-topological_sort.test.cpp"

#include <iostream>
#line 7 "test/simple-topological_sort.test.cpp"

int main() {
	// int V, E; std::cin >> V >> E;
	// std::vector G(V, std::vector(0, 0));
	// for (int _ = 0 ; _ < E ; _++) {
	// 	int s, t; std::cin >> s >> t;
	// 	G[s].push_back(t);
	// }
	// for (const auto& v : zawa::topological_sort(G).get()) {
	// 	std::cout << v << std::endl;
	// }
	std::cout << "Hello World" << std::endl;
}

/*
 * AOJ GRL_4_B トポロジカルソート
 * https://onlinejudge.u-aizu.ac.jp/status/users/zawakasu/submissions/1/GRL_4_B/judge/7516185/C++17
 */

Back to top page