백준 10265 MT

https://www.acmicpc.net/problem/10265 10265번: MT 남규는 동기들과 엠티를 가기 위해 버스를 대절했다. 그런데 과사의 실수로 대절버스의 인원이 잘못되어 남규의 동기들을 모두 태울 수 없었다.

이 와중에 동기들은 화를 내며 다음과 같은 www.acmicpc.net Solved.ac에서는 문제에 SCC태그를 달아놔서 쫄았는데, 풀어 보니 필요 없었다. P4라는 난이도도 부풀려진게 아닐까.

풀이로 넘어가서, 문제 상황만 보면 x_i를 데려가야 i를 데려갈 수 있기에, x_i에서 i로 간선을 연결하고 위상정렬을 하고 싶어진다. SCC가 있을 테니, 그걸 잘 처리하면 될 거 같다고 생각하게 된다.

이제 그래프의 형태를 관찰하면, In-degree가 하나니까 사이클이 하나 있고,.....