문제

• 골드4
  https://acmicpc.net/problem/1043

풀이

• 유니온파인드 (union-find)

유니온 파인드를 통해 같은 파티에 참석하는 사람들과 건너건너 같은 파티에 참석하는 사람들을 한 그룹으로 묶어주었다.
그리고 truth에 있는 원소랑 같은 그룹에 속했다면 이 사람도 거짓말을 하지 못하는 사람이기 때문에 완전탐색으로 찾아 truth에 넣어준다.
이때 이중for문에서 전체 탐색해서 찾아줬는데 전체 탐색하는 이유는 truth가 중간에 업데이트 되면 새롭게 진실을 알게 된 사람과 같은 그룹에 속했지만 이미 탐색한 사람인 경우에는 누락될 수 있기 때문이다.

코드

import sys

input = sys.stdin.readline

#union find 유니온 파인드
N, M = map(int, input().split())

input_truth = list(map(int, input().strip().split()))
truth = set(input_truth[1:])
#truth = input_truth[1:]

party = []
for i in range(M):
    temp = list(map(int, input().strip().split()))
    party.append(temp)


def find(x, parent):
    if x!=parent[x]:
        parent[x] = find(parent[x], parent)

    return parent[x]


def union(a, b, parent):
    a = find(a, parent)
    b = find(b, parent)

    if a<b:
        parent[b] = a
    else:
        parent[a] = b


parent = [i for i in range(N+1)]
count = M

# 가장 작은 값을 기준으로 그룹핑 (굳이 가장 작은 값은 아니어도 됐었을 거 같기도..)
for i in range(M):
    arr = sorted(party[i][1:])
    #print(arr)
    p = arr[0]
    for j in range(1, len(arr)):
        #print(arr[j], arr[j+1])
        # 둘이 같은 그룹이 아니었다면 그룹으로 만들어줌
        if find(p, parent) != find(arr[j], parent):
            union(p, arr[j], parent)

# truth에 있는 원소와 같은 그룹이라면 truth에 넣어준다
visited = [0] * (N+1)
for i in range(1, N+1):
    if i in truth and not visited[i]:
        p = find(i, parent)
        for j in range(1, N+1):
            if find(j, parent)==p:
                visited[j] = 1
                truth.add(j)


# print(parent)
# print(truth)

for i in range(M):
    for j in range(1, party[i][0]+1):
        if party[i][j] in truth:
            count -= 1
            break

print(count)