만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

연결 요소의 개수

면접 대비

시간 제한3초메모리 제한512 MB

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

쉬움10점 중 3점

유형
그래프, DFS
정답자
아직 제출이 없습니다

문제

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

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

입력

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

둘째 줄부터 MM개의 줄에 간선의 양 끝 정점 uu와 vv가 주어진다. (1≤u,v≤N1 \le u, v \le N, u≠vu \ne v) 같은 간선은 한 번만 주어진다.

출력

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

예제4

  1. 예제 1

    입력
    6 5
    1 2
    2 5
    5 1
    3 4
    4 6
    
    예상 출력
    2
    
  2. 예제 2

    입력
    6 8
    1 2
    2 5
    5 1
    3 4
    4 6
    5 4
    2 4
    2 3
    
    예상 출력
    1
    
  3. 예제 3

    입력
    1 0
    
    예상 출력
    1
    
  4. 예제 4

    입력
    2 1
    1 2
    
    예상 출력
    1