6056 : 큐로 구현한 그래프 탐색
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
정점 N개, 간선 E개인 무방향 그래프에서 시작 정점 V로부터 BFS 방문 순서를 출력하시오.
인접 정점이 여러 개이면 정점 번호가 작은 것부터 방문합니다.
[제약 조건]
• 정점 수 $N$: $1 \le N \le 1{,}000$ (정수)
• 간선 수 $E$: $1 \le E \le 10{,}000$ (정수)
• 시작 정점 $V$: $1 \le V \le N$
인접 정점이 여러 개이면 정점 번호가 작은 것부터 방문합니다.
[제약 조건]
• 정점 수 $N$: $1 \le N \le 1{,}000$ (정수)
• 간선 수 $E$: $1 \le E \le 10{,}000$ (정수)
• 시작 정점 $V$: $1 \le V \le N$
입력 설명
첫째 줄에 N (1 ≤ N ≤ 1,000), E (1 ≤ E ≤ 10,000), V.
다음 E줄에 간선 u v.
다음 E줄에 간선 u v.
출력 설명
BFS 방문 순서를 공백으로 구분하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 4 1
1 2
1 3
2 4
3 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1 2 3 4도움
인접 리스트를 정렬한 후 BFS를 수행하면 번호 순으로 방문할 수 있습니다.