6090 : 연결 요소 수 — 무방향 그래프
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
방향성이 없는 그래프가 주어졌을 때, 연결 요소(Connected Component)의 개수를 구하는 프로그램을 작성하십시오.
연결 요소란 서로 연결되어 있는 정점들의 묶음을 의미합니다. 방문하지 않은 모든 노드에 대해 차례대로 DFS를 수행하며 총 호출 횟수를 계산할 수 있습니다.
[제약 조건]
• 정점 수 $N$: $1 \le N \le 1{,}000$ (정수)
• 간선 수 $M$: $0 \le M \le 5{,}000$ (정수)
• 그래프는 무방향입니다.
연결 요소란 서로 연결되어 있는 정점들의 묶음을 의미합니다. 방문하지 않은 모든 노드에 대해 차례대로 DFS를 수행하며 총 호출 횟수를 계산할 수 있습니다.
[제약 조건]
• 정점 수 $N$: $1 \le N \le 1{,}000$ (정수)
• 간선 수 $M$: $0 \le M \le 5{,}000$ (정수)
• 그래프는 무방향입니다.
입력 설명
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 1,000)과 간선의 개수 M (0 ≤ M ≤ 10,000)이 주어집니다.
둘째 줄부터 M개의 줄에 간선의 양 끝 정점 u, v가 주어집니다.
둘째 줄부터 M개의 줄에 간선의 양 끝 정점 u, v가 주어집니다.
출력 설명
주어진 그래프의 연결 요소 개수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
6 5
1 2
2 5
5 1
3 4
4 6
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
모든 노드를 순회하면서 아직 방문하지 않은(visited가 false인) 노드를 발견할 때마다 DFS를 시작하고, 카운터를 1씩 증가시키십시오.