파티에서 거짓말을 할 때 이를 판별할 수 있는 사람과 각 파티에 참석하는 사람이 주어졌을 때, 걸리지 않고 거짓말을 할 수 있는 파티의 수를 출력하는 문제입니다. 백준에서는 분리 집합(Disjoint Set)을 사용해서 풀 수 있다고 했는데, 저는 뭔지 잘 모르겠어서 그냥 그래프로 풀었습니다.
먼저 사람들을 노드로 하는 빈 그래프를 만듭니다. 이제 파티를 입력받으면서 같은 파티에 참석하는 사람들 중 인접한 사람들끼리 그래프의 간선을 만듭니다. 이제 그래프 탐색을 통해서 거짓말을 판별할 수 있는 모든 사람을 찾은 후, 각 파티에 대해 거짓말을 판별할 수 있는 사람이 포함되어있는지 여부를 찾아 없다면 결과값을 1씩 증가시켜 출력하는 방법을 사용했습니다. 근데 왜 이렇게 해도 시간이 0ms인지는 잘 모르겠습니다. 이것도 분리 집합인가
PS알못 OrbitHv의 PS