[백준] 1043번 - 거짓말 (파이썬)

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

# 거짓말
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
know = set(map(int, input().split()[1:]))
party = []
for _ in range(M):
    people = set(map(int, input().split()[1:]))
    party.append(people)

can = [True] * M
for _ in range(M):
    for i, people in enumerate(party):
        if people & know:
            can[i] = False
            know = know | people

result = 0
for i in range(M):
    if can[i]:
        result += 1
print(result)

 

분리 집합

1. 입력을 받으면서 party리스트에 참가자세트를 append

2. 총 파티의 수만큼

    - 각 파티(i)에서 참가멤버(people)와 사실을 알고 있는 사람(know)의 교집합이 존재하면

    - 해당 파티의 can리스트 = False

    - know세트 = know와 people의 합집합으로 업데이트

3. can이 True이면 result += 1

4. result 출력