레이팅 미적용설명
어느 학교에 학생 \(N\)명이 있고, 학생들은 \(1\)번부터 \(N\)번까지 번호가 매겨져 있다. 친구 관계가 \(M\)쌍 주어진다.
친구 관계는 양방향이며, 직접 또는 친구의 친구를 통해 간접적으로 이어진 학생들은 같은 무리에 속한다.
전체 무리의 개수를 구하여라. 친구가 한 명도 없는 학생은 혼자서 하나의 무리를 이룬다.
제약
- \(1 \le N \le 100\,000\)
- \(0 \le M \le 200\,000\)
입력 형식
첫째 줄에 학생 수 \(N\)과 친구 관계 수 \(M\)이 공백으로 주어진다.
다음 \(M\)개의 줄에 각각 친구 관계 \(a\) \(b\)가 주어진다(\(a \ne b\)).
출력 형식
무리의 개수를 출력한다.
예제 1
입력
6 4
1 2
2 3
4 5
4 6출력
2설명
1-2-3 무리와 4-5-6 무리로 나뉘어 무리는 2개이다.
예제 2
입력
4 0출력
4설명
친구 관계가 없어 학생 4명이 각각 혼자 무리를 이루므로 4개이다.
힌트
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
힌트 1
로그인하고 잠금 해제 · 10 🪙
힌트 2
로그인하고 잠금 해제 · 20 🪙
문제 정보
riseoj 작성
출처 Original
태그