1741번 - 반 나누기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 642 | 165 | 125 | 29.138% |
문제
학생들이 너무 떠드는 것을 보다 못한 나머지, 원장님은 결단을 내리셨다. 반을 나누기로.
학생들은 친한 친구들과 떨어지는 것이 싫어서 몹시 거세게 반발했고, 원장님은 이를 잠재우기 위하여 한 가지 방안을 제시하셨다. 인터넷 메신저로 대화할 수 있게 허락해 주신 것이다.
단, 두 사람이 메신저로 대화를 나누기 위해서는 서로가 서로의 메신저 아이디를 알고 있어야 하는데, 모든 학생이 모든 학생의 아이디를 알고 있는 것은 아니다.
이러한 상황에서, 원장님은 최대한 반을 잘게 나누고자 하신다. 다른 반에 속한 학생들끼리는 메신저로 대화해야 하므로, 반드시 서로의 메신저 아이디를 알고 있어야만 한다.
어떤 학생들끼리 서로의 메신저 아이디를 알고 있는지 주어졌을 때, 가장 많은 반을 편성하려면 어떻게 해야 하는지 알아내는 프로그램을 작성하시오.
입력
첫째 줄 학생들의 수 n과, 서로 메신저 아이디를 알고 있는 학생들 쌍의 수 m이 공백을 사이에 두고 주어진다. (2 ≤ n ≤ 100,000. 1 ≤ m ≤ 2,000,000) 이후 m개의 줄에는 서로 메신저 아이디를 알고 있는 학생들 번호의 쌍이 두 개의 정수로 주어진다. 두 학생의 번호는 1이상 n이하의 정수이다.
출력
첫째 줄에, 최대로 편성할 수 있는 반이 몇 개인지 출력한다. 둘째 줄에는, 최대로 편성했을 때 각 반별 인원수를 오름차순으로 출력한다.
예제 입력 1
7 16 1 3 1 4 1 5 2 3 3 4 4 5 4 7 4 6 5 6 6 7 2 4 2 7 2 5 3 5 3 7 1 7
예제 출력 1
3 1 2 4
힌트
4번 학생 혼자 한 반, 5번과 7번 학생 둘이서 한 반, 나머지 학생 네 명이서 한 반이 되도록 반을 편성하면 된다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호