백준 1043 거짓말

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

그래프를 이용하여 해결할 수 있는 문제이다.
나는 파티 배열을 받아서 그래프를 구성하고, 진실을 아는 사람들을 정점으로 그래프를 순회해 가면서 방문한 정점도 진실을 아는 사람으로 변경하였다.

저장해놓은 파티 배열을 돌면서 배열에 있는 원소가 하나라도 진실을 안다면 해당 파티는 참가하지 않는 방식으로 해결하였다.

다른 풀이로는,
union-find 알고리즘을 통해 진실을 아는 사람을 parent로 만들고 파티에 참가한 사람들을 union을 통해 연결하였다.
위와 같이 만들면 파티들을 돌면서 파티 안의 원소를 find를 통해 부모를 찾고 해당 부모가 진실을 알고 있다면 해당 파티를 참가하지 않는다를 코드로 작성하면 된다.

n,m = map(int,input().split())
people = [0]*(n+1)
truth = list(map(int,input().split()))
truth = truth[1:]
for i in range(len(truth)):
    people[truth[i]] = 1
graph = [[] for i in range(n+1)]
party = []
for i in range(m):
    tmp = list(map(int,input().split()))
    tmp = tmp[1:]
    party.append(tmp)
    if len(tmp) == 1:
        continue
    for i in range(len(tmp)):
        for j in range(i+1,len(tmp)):
            graph[tmp[i]].append(tmp[j])
            graph[tmp[j]].append(tmp[i])

for start in truth:
    visited = [0]*(n+1)
    stack = [start]
    while stack:
        x = stack.pop()
        visited[x] = 1
        for j in graph[x]:
            if not visited[j]:
                people[j] = 1
                stack.append(j)
ans = 0
for p in party:
    for x in p:
        if people[x] == 1:
            break
    else:
        ans += 1
print(ans)