위상 정렬

문제

DAG(Directed Acyclic Graph)는 방항셩이 있는 간선으로 이루어진 그래프 중, 사이클이 없는 그래프를 의미한다. DAG에서는 위상 정렬을 항상 할 수 있다.

DAG가 주어질 때, 위상 정렬을 하는 프로그램을 작성하시오.

---

입력

첫 번째 줄에 그래프의 정점의 개수 V, 간선의 개수 E가 공백으로 분리되어 주어진다. (1 ≤ V ≤ 50,000, 1 ≤ E ≤ 100,000)

두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보인 x, y가 공백으로 분리되어 주어진다. 이는 x에서 출발하여 y에 도착하는 유항 간선이 존재한다는 것을 의미한다. (1 ≤ x, y ≤ V, x ≠ y)

주어지는 그래프는 항상 DAG이고, 1번으로 들어오는 간선은 없다.

---

출력

첫 번째 줄에 위상 정렬의 결과를 출력한다. 답이 여러 가지인 경우, 그 중 아무 것이나 출력한다.

---

힌트

입력 예제

4 4

1 2

1 3

2 4

3 4

출력 예제

1 2 3 4

혹은

1 3 2 4

#include <iostream> #include <queue> #include <stack> #include <algorithm> using namespace std; int V, E; //노드개수, 엣지게수, 시작점 vector<int> pathV[100001]; struct Node { int num; int visit; int complete; bool operator < (const Node& n) const { return complete > n.complete; } }; Node nodeInfo[50001]; //DFS 방문배열 int DFS(int S, int count) { //깊이 우선 탐색 if (nodeInfo[S].visit > 0) { //방문완료 return count; } stack<int> DFSS; DFSS.push(S); nodeInfo[S].visit = count++; //방문완료 while (!DFSS.empty()) { int num = DFSS.top(); vector<int>::iterator iter; //간선 순환 for (iter = pathV[num].begin(); iter != pathV[num].end(); iter++) { if (nodeInfo[*iter].visit == 0) { //방문한 적이 없다면 DFSS.push(*iter); nodeInfo[*iter].visit = count++; //방문완료 break; } } if (iter == pathV[num].end()) { //방문이 완료되었다면 nodeInfo[num].complete = count++; DFSS.pop(); } } return count; } int main() { //std::ifstream cin("input.txt"); cin >> V >> E; int a, b; for (int i = 0; i < E; i++) { //간선 입력 cin >> a >> b; pathV[a].push_back(b); } for (int i = 1; i <= V; i++) { nodeInfo[i].num = i; nodeInfo[i].visit = 0; nodeInfo[i].complete = 0; } int count = 1; for (int i = 1; i <= V; i++) { count = DFS(i, count); } sort(nodeInfo + 1, nodeInfo + V + 1); for (int i = 1; i <= V; i++) { cout << nodeInfo[i].num << " "; } cout << endl; //system("pause"); return 0; }