[백준] 1043번 - 거짓말

문제 분석

문제를 통해 알 수 있듯이 같은 파티에 참석한 사람끼리는 같은 이야기를 들을 수 밖에 없다. 이 문제에서 주의해야할 점은 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 듣는 경우 지민이는 거짓말쟁이로 알려지게 된다는 점이다.
따라서 같은 파티에 참석한 인원들을 모두 하나의 같은 집합으로 설계해주는 과정이 필요하다.

소스 코드

# 거짓말

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

people, partyNum = map(int, input().split())
truth = list(map(int, input().split()))
arr = [0] * (people + 1)
temp = []
totalCnt = 0

for i in range(people + 1):
    arr[i] = i

def find(idx):
    if idx == arr[idx]:
        return idx
    else:
        arr[idx] = find(arr[idx])
        return arr[idx]

for _ in range(partyNum):
  partyInfo = list(map(int, input().split()))
  party_people = partyInfo[0]
  if party_people > 0:
      subPartyInfo = partyInfo[1:]
      temp.append(subPartyInfo)
      if len(subPartyInfo) > 1:
          repValue = subPartyInfo[0]
          subPartyInfo = subPartyInfo[1:]
          for v in subPartyInfo:
              arr[find(v)] = find(repValue)

if truth[0] == 0:
    print(partyNum)
else:
  truth = truth[1:]
  for party in temp:
    value = party[0]
    success = True
    for v in truth:
       if find(v) == find(value):
          success = False
          break
    if success:
       totalCnt += 1  
  print(totalCnt)