연결 요소의 개수

정점과 간선으로 주어진 무향 그래프의 연결 요소 개수를 구합니다.

쉬움3그래프DFS면접 대비아직 제출이 없습니다시간 제한3초메모리 제한512 MB

문제

방향 없는 그래프가 주어진다. 이 그래프에 연결 요소(connected component)가 몇 개인지 구하는 프로그램을 작성하시오.

연결 요소는 서로 경로로 이어진 정점의 최대 집합이다. 같은 연결 요소에 속한 두 정점 사이에는 항상 경로가 있고, 서로 다른 연결 요소에 속한 두 정점 사이에는 경로가 없다. 간선이 하나도 닿지 않는 정점도 그 자체로 연결 요소 하나를 이룬다.

입력

첫째 줄에 정점의 개수 NN과 간선의 개수 MM이 공백을 사이에 두고 주어진다. (1N10001 \le N \le 1000, 0MN×(N1)/20 \le M \le N \times (N-1) / 2)

둘째 줄부터 MM개의 줄에 간선의 양 끝 정점 uuvv가 주어진다. (1u,vN1 \le u, v \le N, uvu \ne v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.