R00145
학교 친구 무리
실버 II레이팅
의견: 0
설명
어느 학교에 학생 \(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
태그
평가 및 의견
학교 친구 무리
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
학교 친구 무리
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기