그래프 알고리즘

백준 알고리즘 그래프 그 두 번째 시간
이제는 단순 개념이 아닌 문제풀이로 들어가는 시간이었다.

어려운 문제보다 그래도 푸는 방법만 유추하면 어렵지 않은 문제들

첫 번째 문제는 한 그래프의 bfs와 dfs를 구하는 문제이다.
시작점을 다양하게 주고 bfs의 경우에는 재귀함수를 사용하거나
다른 배열을 사용해서 들어갔을 때 순서를 바꾸어야 한다.
bfs는 단순하게 q를 이용해서 사용할 수 있다. 여기서는 쌍방으로 입출력이 가능한 deque를 사용했다.

from collections import deque

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

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

def bfs(graph, v, visited):
    print()
    visited[v] = True
    q = deque([v])
    while q:
        v = q.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i] and i not in q:
                q.append(i)
                visited[i] = True

    

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for nodes in graph:
    nodes.sort()

visited = [False] * (n + 1)
dfs(graph, v, visited)
visited = [False] * (n + 1)
bfs(graph, v, visited)

두 번째 문제는 문제를 봤을 때 바로 감이 오지 않았지만
정리를 하고 나니까 union_find 문제 같았다.
하지만 오랜만에 보려니 union_find에 관한 개념을 잊어버려서
단순하게 set을 이용해서 set 끼리 교집합이면 union을 해서
아는 사람을 구하고 다시 for를 이용해서 아는 사람이 있는 집합은
제외하고 거짓말을 1씩 증가시켰다.
모든 테스트케이스가 통과했지만 결과는 실패, 이건 다음에 보기로 했다. 더 많은 테스트케이스가 있는 분이 있다면 알려주시면 감사하겠습니다.

n, m = map(int, input().split())
list_1 = list(map(int, input().split()))
k, s = list_1[0], set(list_1[1:])
party = []
ans = 0
for i in range(m):
    list_2 = list(map(int, input().split()))
    party.append([list_2[0], list_2[1:]])


for i in range(m):
    if s.intersection(set(party[i][1])):
        s = s.union(set(party[i][1]))
for i in range(m):
    s2 = set(party[i][1])
    if not s2.intersection(s):
        ans += 1
print(ans)