레이팅 미적용농부 존의 소들은 아침 식사로 시리얼을 가장 좋아한다! 사실, 소들은 식욕이 어찌나 왕성한지 한 끼에 시리얼 한 상자를 통째로 먹어 치운다.
농장은 최근 \(M\)가지 종류의 시리얼이 든 배송을 받았다\((2\le M\le 10^5)\). 안타깝게도 각 시리얼은 한 상자씩뿐이다! \(N\)마리\((1\le N\le 10^5)\)의 소들은 각자 가장 좋아하는 시리얼과 두 번째로 좋아하는 시리얼이 있다. 고를 수 있는 시리얼들이 주어지면, 소는 다음 과정을 수행한다.
- 가장 좋아하는 시리얼 상자가 아직 남아 있으면, 그것을 가지고 떠난다.
- 그렇지 않고 두 번째로 좋아하는 시리얼 상자가 아직 남아 있으면, 그것을 가지고 떠난다.
- 그렇지 않으면, 실망하며 음매 하고 울고는 시리얼을 가져가지 않고 떠난다.
소들의 순서를 최적으로 배열했을 때 굶는 소의 최소 수를 구하라. 또한, 이 최솟값을 달성하는 \(N\)마리 소들의 순열을 아무거나 하나 구하라.
출제자: Dhruv Rohatgi
배점
- \(14\)개 중 \(4\)개의 테스트 케이스에서 \(N,M\le 100\)이다.
- \(14\)개 중 \(10\)개의 테스트 케이스는 추가 제약이 없다.
출제자: Dhruv Rohatgi
첫째 줄에 공백으로 구분된 두 정수 \(N\)과 \(M\)이 주어진다.
각 \(1\le i\le N\)에 대해, \(i\)번째 줄에 \(i\)번째 소가 가장 좋아하는 시리얼과 두 번째로 좋아하는 시리얼을 나타내는, 공백으로 구분된 두 정수 \(f_i\)와 \(s_i\)(\(1\le f_i,s_i\le M\)이고 \(f_i\neq s_i\))가 주어진다.
굶는 소의 최소 수를 출력한 뒤, 이 최솟값을 달성하는 \(1\ldots N\)의 순열을 아무거나 출력한다. 여러 순열이 있으면 그중 아무거나 출력해도 정답으로 인정된다.
8 10
2 1
3 4
2 3
6 5
7 8
6 7
7 5
5 81
1
3
2
8
4
6
5
7In this example, there are \(8\) cows and \(10\) types of cereal.
Note that we can effectively solve for the first three cows independently of
the last five, since they share no favorite cereals in common.
If the first three cows choose in the order \([1,2,3]\), then cow \(1\) will choose
cereal \(2\), cow \(2\) will choose cereal \(3\), and cow \(3\) will go hungry.
If the first three cows choose in the order \([1,3,2]\), then cow \(1\) will choose
cereal \(2\), cow \(3\) will choose cereal \(3\), and cow \(2\) will choose cereal \(4\);
none of these cows will go hungry.
Of course, there are other permutations that result in none of the first three
cows going hungry. For example, if the first three cows choose in the order
\([3,1,2]\) then cow \(3\) will choose cereal \(2\), cow \(1\) will choose cereal \(1\),
and cow \(2\) will choose cereal \(3\); again, none of cows \([1,2,3]\) will go
hungry.
It can be shown that out of the last five cows, at least one must go hungry.
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > January > Silver