[백준] 1043. 거짓말

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

1043번: 거짓말

유니온-파인드로 풀었다. 역시나 부모 찾기는 경로 압축을 이용했다.

입력이 좀 이상하게 주어져서.. 코드가 더럽게 나오긴 했지만..

일단 주어진 사람들끼리 union 해주고, 진실을 아는 사람이 없으면 파티의 개수를 바로 출력한다.

 

진실을 아는 사람이 한명이라도 있다면, 진실을 아는 사람이 속한 집합(부모)를 set()에 넣어주고, 파티에 참석한 사람들이 속한 집합을 for문을 돌며 하나씩 확인해준다.

 

만약 파티에 참석한 사람과 진실을 아는 사람이 속한 집합이 같다면 break를 해주고, 하나의 파티에 진실을 아는 사람과 속한 집합이 같은 사람이 아무도 없다면 즉, 진실을 아는 사람과 파티를 한 사람이 아무도 없다면 break에 걸리지 않으므로 else 에서 정답 수를 +1 해준다. 모든 파티를 확인하면 정답을 print 해주면 된다.

import sys
input = sys.stdin.readline


def find_p(x):
    if p[x] != x:
        p[x] = find_p(p[x])
        return p[x]
    else:
        return x


n, m = map(int, input().split())
know_true = list(map(int, input().split()))
know_true = know_true[1:]
p = [i for i in range(n+1)]
parties = []
for _ in range(m):
    persons = list(map(int, input().split()))
    parties.append(persons)
    for i in range(1, persons[0]+1):
        for j in range(i + 1, persons[0]+1):
            p1 = find_p(persons[i])
            p2 = find_p(persons[j])
            p[p1] = p2

if know_true:
    ans = 0
    know_true_p = set(find_p(x) for x in know_true)
    for party in parties:
        for i in range(1, party[0]+1):
            if find_p(party[i]) in know_true_p:
                break
        else:
            ans += 1
    print(ans)

else:
    print(len(parties))