레이팅 미적용농부 존(Farmer John)은 파티를 열어 소들 몇 마리를 초대하여 자신이 소 무리를 얼마나 아끼는지 보여주고 싶어 한다. 하지만 지난번에 파티에 소를 너무 많이 초대했다가 벌어진 참사를 생생히 기억하기에, 가능한 한 적은 수의 소를 초대하고 싶어 한다.
FJ의 소들 중에는 떼어 놓기 어려운 친구 그룹들이 있다. 그런 어떤 그룹(크기를 k라 하자)에 대해, FJ가 그룹의 소 중 k-1마리 이상을 파티에 초대하면 마지막 소도 초대해야 하며, 결국 그룹 전체가 포함된다. 그룹의 크기는 제한이 없고 서로 겹칠 수도 있지만, 정확히 같은 구성원 집합을 가지는 두 그룹은 없다. 모든 그룹 크기의 합은 최대 250,000이다.
FJ의 소들의 그룹이 주어질 때, 반드시 1번 소를 초대하는 것으로 시작하기로 결정했다면 FJ가 파티에 초대할 수 있는 소의 최소 수를 구하시오 (소들은 편의상 1..N으로 번호가 붙어 있으며, N은 최대 1,000,000이다).
첫째 줄: 공백으로 구분된 두 정수 N (소의 수)과 G (그룹의 수).
둘째 줄부터 1+G번째 줄까지: 각 줄은 소들의 그룹 하나를 설명한다. 그룹의 크기 S를 나타내는 정수로 시작하고, 그 뒤에 그룹에 속한 S마리의 소가 이어진다 (각각 1..N 범위의 정수).
FJ가 파티에 초대할 수 있는 소의 최소 수.
invite.in · 출력을 쓸 파일 invite.out10 4
2 1 3
2 3 4
6 1 2 3 4 6 7
4 4 3 2 14Output details: In addition to cow #1, FJ must invite cow #3 (first group), cow #4 (second group), and cow #2 (final group).
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > January > Silver