유니온 파인드. [1043]

[1. 문제 설명]

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

---

[2. 풀이 접근]

최초에는 모든 파티에 참가할 수 있다고 할 수 있다.

이 후, 어떤 파티에 진실을 아는 사람이 있는 경우 이 파티를 참가하지 않도록 한다.

 

또, 어떤 파티에 진실을 아는 사람이 없는 경우 이 파티에는 무조건 참가가 가능하지는 않다.

이 파티에 참가한 사람이 진실을 모르더라도,

다른 파티에 참석하여 진실을 아는 사람과 만나는 경우에는 결국 진실을 알게 될 것이기 때문이다.

 

따라서 모든 파티에 참가자가 서로 만날 것인가에 대한 여부를 먼저 처리해야 한다.

전처리를 먼저하고 나서 파티 참석 여부를 따져야 한다는 것이다.

 

전처리는 아래와 같이 진행한다.

1. 진실을 아는 사람들을 하나의 집합에 속하게 한다.
2. 각 파티에 속한 사람들을 하나의 집합에 속하게 한다.

전처리 후 각 파티에 참여한 사람들이 진실을 아는 사람 집합에 속하게 되는 경우

그 파티는 참여하지 않도록 결과를 만들면 된다.

---

[3. 코드]