<commit_before>#pragma once
#include <vector>

#include "graph/graph.hpp"

template<typename T = long long, size_t MASK = 0>
class DirectedGraph : public Graph<T, MASK> {
public:
	DirectedGraph() : DirectedGraph(0) {}
	DirectedGraph(const size_t vertices_count) : Graph<T, MASK>(vertices_count) {}

	bool top_sort_acyclic(std::vector<size_t>* vertex_order = nullptr) const;
	void top_sort_rec(std::vector<size_t>* vertex_order) const;

	DirectedGraph reversed() const;
	
	size_t scc(std::vector<size_t>* vertex_color = nullptr) const;

private:
	void top_sort_rec_impl(const size_t vertex, std::vector<size_t>& order, std::vector<bool>& used) const;

};

template<typename T, size_t MASK>
DirectedGraph<T, MASK> DirectedGraph<T, MASK>::reversed() const {
	DirectedGraph<T, MASK> result;
	result.init(this->vertices_count_);
	for (const auto& edge : this->edges()) {
		result.add_directed_edge(edge.reversed());
	}
	return result;
}

template<typename T, size_t MASK>
bool DirectedGraph<T, MASK>::top_sort_acyclic(std::vector<size_t>* vertex_order) const
// non-recursive topological sorting, works only for acyclic graphs 
{
	std::vector<size_t> order;
	std::vector<size_t> inbound_degree(this->vertices_count_, 0);
	for (const auto& to : this->to_) {
		++inbound_degree[to];
	}
	for (const size_t i : this->vertices()) {
		if (inbound_degree[i] == 0) {
			order.emplace_back(i);
		}
	}
	size_t head = 0;
	while (head < order.size()) {
		const size_t cur_vertex = order[head++];
		for (const auto& it : this->edges(cur_vertex)) {
			const size_t to = it.to();
			--inbound_degree[to];
			if (inbound_degree[to] == 0) {
				order.emplace_back(to);
			}
		}
	}
	if (vertex_order != nullptr) {
		vertex_order->swap(order);
	}
	return order.size() == this->vertices_count_;
}

template<typename T, size_t MASK>
void DirectedGraph<T, MASK>::top_sort_rec(std::vector<size_t>* vertex_order) const {
	std::vector<bool> used(this->vertices_count_, false);
	std::vector<size_t> order;
	for (const size_t v : this->vertices()) {<commit_msg>Fix bug in DirectedGraph::top_sort_acyclic() and added is_acyclic() method.<commit_after>#pragma once
#include <vector>

#include "graph/graph.hpp"

template<typename T = long long, size_t MASK = 0>
class DirectedGraph : public Graph<T, MASK> {
public:
	DirectedGraph() : DirectedGraph(0) {}
	DirectedGraph(const size_t vertices_count) : Graph<T, MASK>(vertices_count) {}

	bool is_acyclic() const;
	bool top_sort_acyclic(std::vector<size_t>* vertex_order = nullptr) const;
	void top_sort_rec(std::vector<size_t>* vertex_order) const;

	DirectedGraph reversed() const;
	
	size_t scc(std::vector<size_t>* vertex_color = nullptr) const;

private:
	void top_sort_rec_impl(const size_t vertex, std::vector<size_t>& order, std::vector<bool>& used) const;

};

template<typename T, size_t MASK>
DirectedGraph<T, MASK> DirectedGraph<T, MASK>::reversed() const {
	DirectedGraph<T, MASK> result;
	result.init(this->vertices_count_);
	for (const auto& edge : this->edges()) {
		result.add_directed_edge(edge.reversed());
	}
	return result;
}

template<typename T, size_t MASK>
bool DirectedGraph<T, MASK>::is_acyclic() const {
	return this->top_sort_acyclic();
}

template<typename T, size_t MASK>
bool DirectedGraph<T, MASK>::top_sort_acyclic(std::vector<size_t>* vertex_order) const
// non-recursive topological sorting, works only for acyclic graphs 
{
	std::vector<size_t> order;
	std::vector<size_t> inbound_degree(this->vertices_count_, 0);
	for (const auto& to : this->to_) {
		++inbound_degree[to];
	}
	for (const size_t i : this->vertices()) {
		if (inbound_degree[i] == 0) {
			order.emplace_back(i);
		}
	}
	size_t head = 0;
	while (head < order.size()) {
		const size_t cur_vertex = order[head++];
		for (const auto& it : this->edges(cur_vertex)) {
			const size_t to = it.to();
			--inbound_degree[to];
			if (inbound_degree[to] == 0) {
				order.emplace_back(to);
			}
		}
	}
	const bool result = (order.size() == this->vertices_count_);
	if (vertex_order != nullptr) {
		vertex_order->swap(order);
	}
	return result;
}

template<typename T, size_t MASK>
void DirectedGraph<T, MASK>::top_sort_rec(std::vector<size_t>* vertex_order) const {
	std::vector<bool> used(this->vertices_count_, false);
	std::vector<size_t> order;
	for (const size_t v : this->vertices()) {
{'fraction_non_alphanumeric': 0.14960446719404374, 'fraction_numerical': 0.002791996277338297, 'mean_word_length': 5.654798761609907, 'pattern_counts': {'":': 0, '<': 53, '<?xml version=': 0, '>': 72, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7296603', 'n_tokens_mistral': 1679, 'n_tokens_neox': 1595, 'n_words': 346}