이번 문제는 유니온-파인드 알고리즘을 통해 해결하였다. 문제를 보자마자 유니온-파인드를 통해 각각의 부모를 찾고, 강의실 순서를 순회하며 부모가 다를 경우에 결과 변수를 증가시키면 되겠다 생각하였고, 그렇게 구현하였다. 유니온-파인드를 진행하여도, 완전히 부모를 찾지 못했을 수도 있기 때문에 시간이 충분하다면 정답을 위해 부모를 비교할 때, find함수를 통해 다시 한번 부모를 찾는 것이 좋을 것 같다는 생각이 들었다.

Code

n, m = map(int, input().split())
parents = [i for i in range(n+1)]
def find(a):
    if a != parents[a]:
        parents[a] = find(parents[a])
    return parents[a]
def union(a, b):
    a = find(a)
    b = find(b)
    if a < b:
        parents[b] = a
    else:
        parents[a] = b
for _ in range(m):
    a, b = map(int, input().split())
    union(a, b)
path = list(map(int, input().split()))
answer = 0
for i in range(n-1):
    if find(path[i]) != find(path[i+1]):
        answer += 1
print(answer)