1043 거짓말

everyone,party_num=map(int,input().split()) #사람들 수, 파티의 개수
know=set(map(int,input().split(' ')[1:]))#아는 사람들 set
parties=[]
count=0 #과장해서 말할 수 있는 파티 개수

for i in range(0,party_num):
    party=set(map(int,input().split()[1:]))# 파티 set
    parties.append(party)

for i in range(0,party_num):#나중에 알게된 파티가 있으면 먼저 있던 파티도 진실을 알게 되므로 파티 횟수만큼 반복
    for party in parties:
        if party&know:#아는 사람이 참석한 파티를 know에 추가
            know=know.union(party)
                        
for party in parties:
    if party&know:
        continue
    count=count+1
        
print(count)

 파티에 참석한 사람들 중에 진실을 아는 사람이 있다면, 그 파티에 참석한 사람은 모두 진실을 아는 사람이 된다.

 

그럼 그 파티와 교집합이 있는 모든 파티도 진실을 아는게 된다.

 

진실을 아는 파티에 참석한 사람들을 모두 know집합에 union하면 진실을 아는 사람들 집합을 구할 수 있다.