6107 : DFS 종합 1 — DFS 기법 통합
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
다양한 DFS 관련 문제 유형들을 해결할 수 있는 종합 처리 프로그램을 작성하십시오. 프로그램은 Q개의 줄에 걸쳐 다음과 같은 형식의 쿼리 명령들을 처리해야 합니다.
명령어 유형:
1.
2.
3.
위상 정렬 방문 규칙:
DFS 시작 노드 선택 시 1부터 N까지 오름차순으로 방문을 시도하고, 인접 노드 방문 시 번호가 작은 노드부터 방문합니다. DFS 완료 순서(post-order)의 역순으로 위상 정렬을 완성합니다.
명령어 유형:
1.
COMP N M u1 v1 u2 v2 ...: N개 정점과 M개 간선으로 구성된 무방향 그래프의 연결 요소 수를 구합니다.2.
CYCLE N M u1 v1 u2 v2 ...: N개 정점과 M개 간선으로 구성된 무방향 그래프의 사이클 존재 여부를 판단하여 YES 또는 NO를 구합니다.3.
TOPO N M u1 v1 u2 v2 ...: N개 정점과 M개 간선으로 구성된 방향 그래프에 대해 위상 정렬을 수행합니다. 위상 정렬이 불가능할 경우 IMPOSSIBLE을 출력합니다.위상 정렬 방문 규칙:
DFS 시작 노드 선택 시 1부터 N까지 오름차순으로 방문을 시도하고, 인접 노드 방문 시 번호가 작은 노드부터 방문합니다. DFS 완료 순서(post-order)의 역순으로 위상 정렬을 완성합니다.
입력 설명
첫째 줄에 처리할 명령 쿼리의 수 Q (1 ≤ Q ≤ 10)가 주어집니다.
둘째 줄부터 Q개의 줄에 걸쳐 명령의 종류 TYPE(COMP, CYCLE, TOPO)과 N, M, 그리고 공백으로 구분된 E개의 간선 정보가 한 줄에 모두 주어집니다.
둘째 줄부터 Q개의 줄에 걸쳐 명령의 종류 TYPE(COMP, CYCLE, TOPO)과 N, M, 그리고 공백으로 구분된 E개의 간선 정보가 한 줄에 모두 주어집니다.
출력 설명
Q개의 줄에 걸쳐 각 쿼리의 수행 결과를 한 줄에 하나씩 순서대로 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
COMP 4 3 1 2 2 3 3 4
CYCLE 3 3 1 2 2 3 3 1
TOPO 4 4 1 2 1 3 2 4 3 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1
YES
1 3 2 4도움
각각의 명령어 유형에 맞게 이전에 사용했던 연결 요소 카운트 DFS, 무방향 사이클 판정 DFS, 그리고 위상 정렬용 Post-order DFS 함수들을 하나의 클래스나 파일에 묶어서 모듈식으로 실행하십시오.