[백준] 1043 거짓말 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/1043
• 🔑 union, find [유니온 파인드]
  1. 진실을 아는 사람들을 모두 같은 번호로 묶어준다. union
  2. 각 파티마다 오는 사람들을 모두 같은 번호로 묶어준다. union
     1. 진실을 아는 사람들이 오는 파티면 1번 과정에서의 그룹에 포함된다.
  3. 진실을 아는 사람들의 그룹과, 각 파티의 그룹이 겹치지 않으면 거짓말을 한다. find
  4. 거짓말할 수 있는 파티의 개수를 세면 끝 ✨
     1. 예외로 진실을 아는 사람이 없으면 파티의 횟수를 출력하고 종료했다.

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

parent = [i for i in range(n+1)]
true = list(map(int, input().split()))  # 진실을 아는 사람 수, 번호
partys = [list(map(int, input().split())) for _ in range(m)]

def union(a, b):
    x = find(a)
    y = find(b)
    parent[y] = x

def find(x):
    if parent[x] == x:
        return parent[x]
    parent[x] = find(parent[x])
    return parent[x]

if true[0] == 0:                # 진실을 아는 사람이 없으면 모든 파티에서 거짓말 가능
    print(m)
    exit()

for i in range(2, len(true)):   # 진실을 아는 사람 union
    union(true[1], true[i])

for party in partys:            # 파티마다 사람들 union
    for i in range(2, len(party)):
        union(party[1], party[i])

answer = 0
x = find(true[1])

for party in partys:
    if find(party[1]) != x:
        answer += 1

print(answer)