위상정렬이란? DAG(Directed Acyclic Graph, 방향이 있고 사이클이 없는 그래프)에서 방향을 거스르지 않고 나열하는 것을 위상정렬이라고 한다. 예를 들어 이 그래프에서 위상정렬을 하면 1->2->4->3 또는 1->2->3->4가 결과로 나올 수 있다.(위상정렬의 결과는 여러가지일 수 있다.) DFS를 이용한 구현 dfs를 수행하며 방문한 정점의 순서를 구하면 된다. dfs를 수행하며 dfs가 종료되는 순서를 기록한 후 이를 뒤집어주면 된다. 방문하는 정점들을 스택에 집어넣고 차례대로 꺼내면서 출력해줘도 된다. 아래 코드는 방문한 정점들을 벡터에 집어넣고 벡터를 뒤집었다. #include #include #include using namespace std; int n, m; bool v..
