[백준] 1043번 : 거짓말

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

1043번: 거짓말

해당 문제는 파티리스트들을 2번 스캔 해야합니다.

진실을 알고 있는 사람과 같은 파티에 참석할 경우 해당하는 파티원들은 모두 진실만 들을 수 있습니다.

따라서 파티 리스트들을 한번 스캔하는데 진실을 알고있는 사람들의 그룹을 만듭니다. ( 파이썬 set 자료구조 사용 )

두번째 스캔에는 파티원들 모두 진실을 알고 있는 그룹에 속하지 않아야 지민이는 거짓말을 할 수 있습니다.

 

 

N, M = map(int, input().split()) 
graph = list(map(int, input().split()))

truthPeopleCount = graph[0]
truthPeopleList = set(graph[1:])

partyList = [list(map(int, input().split()))[1:] for _ in range(M)]

updated = True
while updated:
    updated = False
    for party in partyList:
        if any(person in truthPeopleList for person in party):
            if not truthPeopleList.issuperset(party): # 새로운 사람을 추가하는지 확인
                truthPeopleList = truthPeopleList.union(party)
                updated = True

counter = sum(1 for party in partyList if not any(person in truthPeopleList for person in party))
print(counter)