1741번 - 반 나누기
Lemma 1. u, v가 반드시 같은 반에 속한다 <=> u, v가 서로의 메신저 아이디를 모른다.
따라서, G = (V, E)를 V = 학생들, E = {(u, v) | u, v가 서로의 메신저 아이디를 모른다}라고 정의하면, G의 각 connected component는 반드시 통째로 같은 반에 배정되어야 합니다.
그런데 반을 최대한 잘게 나누는 것이 목적이므로, G의 각 connected component를 독립적인 반으로 인정하는 것이 최선입니다.
따라서 말씀하신 것과 같은 경우는 발생하지 않습니다.
댓글을 작성하려면 로그인해야 합니다.
josephwon0310 6년 전 0
예를들어 n명의 학생과 m개의 엣지가 주어졌을시, 그래프의 모양에따라
최대 반의 수는 같은데 각 반의 학생수가 다르게 나올수가 있나요?
10명의 학생일 경우
3
1, 4, 5 인 경우와
3
3, 3, 4 같은 경우가 있을 수 있나요?