문제

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

문제접근

둘 째 줄에 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 이걸 set에 넣고 m개의 파티 정보를 순회하며 해당 파티에 set에 있는 사람이 있는지를 확인만 하면 되는거 아닌가 라고 쉽게 생각했다.
하지만! 모르던 사람도 파티에서 진실을 들은 순간 그 사람도 진실을 아는게 되어버린다.
그래서 해시를 사용한 방법은 더이상 안된다고 판단했다.

그래프로 접근하는 방법을 생각했다.
1. 처음에 진실을 아는 사람을 기점으로 DFS/BFS 탐색을 해서 진실을 아는 사람의 범위를 구한다.
2. 전체탐색하며 진실을 아는사람이 파티에 있는지 확인한다.

코드

from sys import stdin

input = stdin.readline


def dfs(i):
    visited[i] = 1
    truth[i] = 1
    for j in people[i]:
        if visited[j]:
            continue
        dfs(j)


n, m = map(int, input().split())
t = list(map(int, input().split()))
truth = [0 for _ in range(n + 1)]
for i in t[1:]:
    truth[i] = 1
ans = 0
people = [[] for _ in range(n + 1)]
visited = [0 for _ in range(n + 1)]
party = []
for _ in range(m):
    tmp = list(map(int, input().split()))
    party.append(tmp)
    for i in tmp[1:]:
        for j in tmp[1:]:
            if j == i:
                continue
            people[i].append(j)
for i in t[1:]:
    if visited[i]:
        continue
    dfs(i)
for i in party:
    if sum(truth[j] for j in i[1:]):
        continue
    ans += 1
print(ans)

복잡도 분석

N, M은 50 이하의 자연수이고, 진실을 아는 사람의 수는 0 이상 50 이하의 정수, 각 파티마다 오는 사람의 수는 1 이상 50 이하의 정수

시간 복잡도

처음에 m개의 파티 정보를 받으며 한 파티당 최대 50명이고 파티 안에서 한명 당 최대 49명씩 이어진다.
그럼 최대 m=n<=50 이니까 O(n^3)으로 표현할 수 있다고 생각한다.
채점결과 : 56ms

공간 복잡도

채점 결과 : 31120KB

학습포인트

그래프 이론
그래프 탐색
자료 구조
분리 집합
다른 방법으로 접근해보기.