6104 : 역방향 그래프 — 방향 그래프 역전
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
방향 그래프가 주어졌을 때, 모든 간선의 방향을 정반대로 뒤집은 역방향 그래프(Transpose Graph)를 생성하고 원본 그래프와 역방향 그래프 각각에서 시작 정점 S로부터 DFS를 돌려 방문 노드 순서를 비교해 보려 합니다.
탐색 규칙:
두 DFS 탐색 시 인접 노드를 방문하는 순서는 정점 번호가 작은 것부터 방문하도록 고정합니다.
탐색 규칙:
두 DFS 탐색 시 인접 노드를 방문하는 순서는 정점 번호가 작은 것부터 방문하도록 고정합니다.
입력 설명
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 1,000), 방향 간선의 개수 M (1 ≤ M ≤ 5,000), 시작 노드 S (1 ≤ S ≤ N)가 주어집니다.
둘째 줄부터 M개의 줄에 방향 간선 u v가 주어집니다.
둘째 줄부터 M개의 줄에 방향 간선 u v가 주어집니다.
출력 설명
첫째 줄에 원본 그래프에서 시작한 DFS 방문 순서를 공백 구분하여 출력합니다.
둘째 줄에 역방향 그래프에서 시작한 DFS 방문 순서를 공백 구분하여 출력합니다.
둘째 줄에 역방향 그래프에서 시작한 DFS 방문 순서를 공백 구분하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 4 1
1 2
2 3
3 4
4 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1 2 3 4
1 4 3 2도움
역방향 그래프는 원본 간선
u -> v가 주어질 때 v -> u 형태로 뒤집어서 인접 리스트를 표현하면 쉽게 구현할 수 있습니다.