<종만북> 28. DFS_위상정렬 (TopologicalSort) c++

앞에서 했던 위상정렬이 inDegree 즉, 진입차수의 개수를 이용하여 풀었다면 이번에는 조금 다른 방법으로 접근한다.

visited 함수를 두어 모든 정점들을 방문하고, 각 정점에서 간선으로 연결된 다음 정점을 방문하며 order에 기록해둔다.

모든 순회가 끝나고 나면 order의 순서를 뒤집는다
(가장 나중에 호출되는 게 가장 먼저 기록되기 때문에)

void dfs(int current) {
	visited[current] = true;

	for (int next = 0; next < adj.size(); next++) {
		if (adj[current][next] && !visited[next])
			dfs(next);
	}
	order.push_back(current);
}

vector<int> topologicalSort() {
	int m = adj.size();
	visited = vector<bool>(m, false);
	order.clear();

	for (int i = 0; i < adj.size(); i++)
		if (!visited[i]) dfs(i);

	reverse(order.begin(), order.end());

	return order;
}