6103 : DFS 트리 — DFS 스패닝 트리
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
무방향 연결 그래프와 탐색을 시작할 정점 S가 주어집니다. S 정점부터 시작하여 DFS를 수행할 때 발생하는 DFS 스패닝 트리를 구하고, 트리 간선(Tree Edge)과 역방향 간선(Back Edge)을 분류하여 출력하는 프로그램을 작성하십시오.
규칙 및 정렬:
1. 인접한 노드를 방문할 때는 번호가 작은 정점부터 방문합니다.
2. 모든 간선 출력 시 작은 번호 정점이 왼쪽으로 가게 정렬하여
3. 트리 간선 목록과 백 간선 목록은 각각 u를 기준으로 오름차순, u가 같으면 v를 기준으로 오름차순 정렬하여 출력합니다.
규칙 및 정렬:
1. 인접한 노드를 방문할 때는 번호가 작은 정점부터 방문합니다.
2. 모든 간선 출력 시 작은 번호 정점이 왼쪽으로 가게 정렬하여
u v 형태로 출력해야 합니다. (u < v)3. 트리 간선 목록과 백 간선 목록은 각각 u를 기준으로 오름차순, u가 같으면 v를 기준으로 오름차순 정렬하여 출력합니다.
입력 설명
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 500), 간선의 개수 M (1 ≤ M ≤ 5,000), 시작 정점 S (1 ≤ S ≤ N)가 주어집니다.
둘째 줄부터 M개의 줄에 무방향 간선 u v가 주어집니다.
둘째 줄부터 M개의 줄에 무방향 간선 u v가 주어집니다.
출력 설명
첫째 줄에 트리 간선의 개수 T를 출력합니다.
둘째 줄부터 T개의 줄에 걸쳐 트리 간선 u v를 정렬 순서대로 출력합니다.
다음 줄에 백 간선의 개수 B를 출력합니다.
이후 B개의 줄에 걸쳐 백 간선 u v를 정렬 순서대로 출력합니다.
둘째 줄부터 T개의 줄에 걸쳐 트리 간선 u v를 정렬 순서대로 출력합니다.
다음 줄에 백 간선의 개수 B를 출력합니다.
이후 B개의 줄에 걸쳐 백 간선 u v를 정렬 순서대로 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 4 1
1 2
2 3
3 4
4 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3
1 2
2 3
3 4
1
1 4도움
DFS 탐색 과정에서 처음 방문하는 노드를 가리키는 간선은 트리 간선(Tree Edge)입니다. 이미 방문한 노드를 가리키며 부모 노드가 아닌 노드로 향하는 간선은 백 간선(Back Edge)으로 분류할 수 있습니다.