백준 1043. 거짓말

https://www.acmicpc.net/problem/1043

1043번: 거짓말

 

주어지는 진실을 아는 사람들의 번호를 큐에 넣는다.

다음을 큐가 빌때까지 반복한다.

각 파티를 탐색하면서 진실을 아는 사람이 한명이라도 있다면 나머지 인원중 아직 기록하지 않은 사람들을 진실을 아는 사람들의 큐에 넣고 기록한다. 

 

사람의수, 파티의수가 50 이하로 엄청 작기 때문에 모조리 탐색하도록 짰는데, 정렬을 한다던가 하면 속도가 더 빨라질것 같긴 하다.

근데 그냥 모두 탐색해도 0ms가 나온다.

 

 

---

다른 분들 답을 보니 Union-Find 알고리즘을 사용해서 푼분들이 많아서 Union-Find를 사용해서 풀어봤다.

같은 파티에 속한 사람들을 Union 한다. (같은 부모를 갖게한다.)

진실을 알고있는 사람과 부모가 같은 참가원이 있는 파티는 과장된 이야기를 할 수 없는 파티다.