class TopologicalSort
{
private:
	enum class STATUS
	{
		UN_VISITED,
		IN_SEARCHING,
		FINISHED
	};

	vector<vector<int>> edges;
	vector<STATUS> visited;
	vector<int> sequence;

	bool find_cycle = false;       // cycle

	/**
	 * @brief		deep first search
	 * @param[in]	node index
	 *
	 */
	void deepFirstSearch(int node)
	{
		visited[node] = STATUS::IN_SEARCHING;
		for (int neighbor : edges[node]) {
			if (visited[neighbor] == STATUS::UN_VISITED) {
				deepFirstSearch(neighbor);
				if (find_cycle) {
					return;  // unsolvable
				}
			}
			else if (visited[neighbor] == STATUS::IN_SEARCHING) {
				find_cycle = true;
				return;
			}
		}
		visited[node] = STATUS::FINISHED;
		sequence.push_back(node);
	}

public:
	/**
	 * @brief       topological sequence
	 * @param[in]	number of nodes
	 * @param[in]   node connection
	 * @retval		sequence
	 */
	vector<int> findTopologicalOrder(int numNodes, vector<vector<int>>& linkage)
	{
		edges.resize(numNodes);
		visited.resize(numNodes, STATUS::UN_VISITED);

		// generate adjacency list
		for (const auto& info : linkage) {
			edges[info[1]].push_back(info[0]);
		}

		//  deep first search to determine the topological sequence
		for (int i = 0; i < numNodes && !find_cycle; ++i) {
			if (visited[i] == STATUS::UN_VISITED) {
				deepFirstSearch(i);
			}
		}

		if (find_cycle) {
			return vector<int>();   //  unsolvable for cycle
		}

		reverse(sequence.begin(), sequence.end());
		return sequence;
	}
};