거짓말

Baekjoon1043

Step1: Problem Analysis
집합의 기준은 party!
과장된 이야기를 할 수 있는 파티의 최댓값은 결국 진실을 알 수 없는 사람이 있는 party라면 그 개수를 세어야 된다는 뜻!

Solution
-Union-Find 알고리즘
-인원 수 만큼의 집합 생성! -답 구하기
Union-Find 알고리즘을 사용해 파티마다 탐색하며 거짓말쟁이가 아니라면 union하고 거짓말쟁이라면 union을 하지 않아서 거짓말쟁이와 거짓말쟁이가 아닌 집합을 나눈다.
다 같은 그룹이라면 거짓말을 할 수 있는 환경이라는 뜻이므로 answer에 1을 더하고 다른 그룹 여러 개가 있다면 진실을 아는 사람들이 있다는 뜻으로 answer을 그냥 0으로 나두는 식으로 파티마다 탐색해서 파티 갯수 최대값을 구한다!

Step2: Solve Manually

Step3: Pseudo Code

Step4: Implement Code
1st attempt

2nd attempt (Book)

Time Complexity : MTlogN
3rd attempt

Time Complexity : MT^3