6098 : 위상 정렬 DFS — 역방향 DFS
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
방향성 비사이클 그래프(DAG)가 주어졌을 때, 모든 노드를 순서대로 위상 정렬(Topological Sort)하는 프로그램을 작성하십시오.
정렬 규칙:
1. DFS 역순(Post-order finish time의 역순) 방식을 사용하여 위상 정렬을 구현합니다.
2. DFS를 시작할 정점은 1번부터 N번까지 오름차순으로 탐색을 시도합니다.
3. DFS 탐색 시 인접한 다음 정점을 방문할 때는 번호가 작은 정점부터 순서대로 방문합니다.
[제약 조건]
• 정점 수 $N$: $1 \le N \le 1{,}000$ (정수)
• 간선 수 $M$: $0 \le M \le 5{,}000$ (정수)
• 입력 그래프는 DAG(방향성 비사이클 그래프)입니다.
정렬 규칙:
1. DFS 역순(Post-order finish time의 역순) 방식을 사용하여 위상 정렬을 구현합니다.
2. DFS를 시작할 정점은 1번부터 N번까지 오름차순으로 탐색을 시도합니다.
3. DFS 탐색 시 인접한 다음 정점을 방문할 때는 번호가 작은 정점부터 순서대로 방문합니다.
[제약 조건]
• 정점 수 $N$: $1 \le N \le 1{,}000$ (정수)
• 간선 수 $M$: $0 \le M \le 5{,}000$ (정수)
• 입력 그래프는 DAG(방향성 비사이클 그래프)입니다.
입력 설명
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 1,000)과 방향 간선의 개수 M (0 ≤ M ≤ 5,000)이 주어집니다.
둘째 줄부터 M개의 줄에 걸쳐 방향 간선 u v (u에서 v로 이동 가능)가 주어집니다.
둘째 줄부터 M개의 줄에 걸쳐 방향 간선 u v (u에서 v로 이동 가능)가 주어집니다.
출력 설명
위상 정렬을 수행한 결과를 정점 번호로 공백을 구분하여 한 줄에 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 4
1 2
1 3
2 4
3 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1 3 2 4도움
DFS 호출이 끝난(더 이상 갈 곳이 없는) 시점에 정점 번호를 스택이나 리스트에 저장합니다. 모든 탐색이 끝난 후 이 저장된 리스트를 역순으로 뒤집으면 위상 정렬 결과를 얻을 수 있습니다.