11.28 알고리즘 문제풀이

 

코테 준비

 

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

1043번: 거짓말

import sys
input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())
knowns = set(map(int, input().split()[1:]))
party = [list(map(int, input().split()[1:])) for _ in range(M)]
visited = [False] * (N+1)

q = list(knowns)
while q:
    known = q.pop()
    visited[known] = True
    
    for attendees in party:
        if known in attendees:
            for attendee in attendees:
                if not visited[attendee]:
                    knowns.add(attendee)
                    q.append(attendee)

result = 0
for attendees in party:
    flag = True
    for known in knowns:
        if known in attendees:
            flag = False
            break
    if flag:
        result += 1

print(result)

I=lambda:[*map(int,input().split())]
n,m=I()
c,*k=I()
k={*k}
p=[{*I()[1:]}for _ in range(m)]
for i in p:
    for i in p:
        if i&k:k|=i
r=0
for i in p:
    if not i&k:r+=1
print(r)

 

재밌는 답안이 있었다.

교집합을 이용하면 연산을 간단하게 구현할 수 있음을 배웠다.

for i in p: 가 반복되는 것도 인상적이었다.