진실을 아는 사람이 포함되는 모든 파티에서는 거짓말을 하지 않는다. 따라서 모든 사람들의 연결요소를 찾아야 한다. 따라서 유니온 파인드를 활용한다.
union으로 연결할 때 진실을 아는 사람이 부모가 되는 방향으로 합쳐나간다.
둘 다 진실을 알지 않다면, 부모가 누가 되는지는 상관 없다.
파티에 5명이 참석하면 첫번째 사람을 2~4번째 사람과 union 연산을 한다. 그럼 5명을 합집합으로 연결한 것이 된다.
모든 파티에서 연결해줬으면, 다시 파티를 순회하며 첫번째 사람의 부모가 진실을 아는 사람들의 집합에 속해있는지 확인한다.
속해있으면 파티를 갈 수 없고, 속하지 않으면 파티에 참석할 수 있다.
def find(x):
if x != par[x]:
par[x] = find(par[x]) # 경로압축
return par[x]
def union(a, b):
a = par[a]
b = par[b]
if a in trues: # 진실을 아는 사람이 부모가 되는 방향으로 합친다.
par[b] = a
else:
par[a] = b
n, m = map(int, input().split())
trues = list(map(int, input().split())) # 진실을 아는 사람들
arr = [list(map(int, input().split())) for _ in range(m)]
par = [i for i in range(n + 1)]
cnt = m # 모든 파티에 참석하는 경우를 default로
if trues[0]:
trues = trues[1:]
for i in range(m):
if arr[i][0] == 1: # 파티에 혼자 참석하는 경우
continue
for j in range(2, len(arr[i])): # 각각의 파티원들을 하나의 합집합으로 연결한다.
if find(arr[i][1]) == find(arr[i][j]): # 이미 같은 집합에 속해있는 경우
continue
union(arr[i][1], arr[i][j]) # 첫번째 사람과 나머지 사람들을 한 번씩 연결한다.
for i in range(m): # 파티를 다시 순회하며 진실을 아는 사람들의 집합에 속해있는 지 확인
if find(arr[i][1]) in trues: # 어차피 다 합집합으로 연결되어있으니 한 명만 파악하면 된다.
cnt -= 1
print(cnt) # 갈 수 있는 파티의 개수를 출력한다.