친구관계와 친구비가 주어졌을 때, 자신이 가진 돈으로 모든 사람과 친구가 될 수 있으면 최소의 친구비를, 그렇지 않다면 Oh no를 출력하는 문제입니다. 이 문제의 주인공은 “친구의 친구는 친구다”라는 놀라운 논리로 친구비를 최소로 사용하고 싶어합니다. 이를 확장하면 친구관계를 그래프로 나타냈을 때 두 학생 사이에 경로가 존재하면 친구라는 것입니다. 그러면 이 경로를 포함한 하나의 그래프에 속하는 학생 중 친구비가 가장 적은 학생에게 친구비를 내면 이 그래프에 속하는 모든 학생과 친구가 되는 것입니다. 다르게 생각하면 각 독립적인 집합마다 친구비를 제공해야합니다. 따라서 주어진 관계를 바탕으로 분리 집합을 구성하고, 각 집합마다 최소의 친구비를 구하여 그 합이 자신이 가진 돈보다 적은지 판단합니다. 적다면 그 합을, 아니라면 Oh no를 출력하면 됩니다.
PS알못 OrbitHv의 PS