📅 2026-05-10 (일)

🎯 오늘 학습한 목표

• Disjoint-set 1문제 풀기

---

1. 경로의 적합성 판단 2

n개의 정점과 m개의 간선으로 이루어진 양방향 그래프가 있습니다.

k개의 점으로 이루어진 순서가 주어졌을 때, 그래프 위에서 주어진 순서대로 이동하는 것이 가능한지를 판단하는 프로그램을 작성해보세요.

입력

첫 번째 줄에 정점의 개수 n, 간선의 수 m, 그리고 순서의 길이 k;가 공백을 사이에 두고
주어집니다.

두 번째 줄부터 m개의 줄에 걸쳐 간선에 대한 정보 (x, y)가 공백을 사이에 두고 주어집니다.
이는 두 정점 x, y가 간선을 통해 연결되어 있음을 뜻하며, 동일한 간선이 여러번 주어지는
경우는 없다고 가정해도 좋습니다.

마지막 줄에는 k개의 점으로 이루어진 순서 정보가 공백을 사이에 두고 순서대로 주어집니다.

제한 조건

·1≤n,m≤100,000
·1≤k≤100,000
·1≤x,y≤n,x≠y

출력

주어진 순서대로 이동하는 것이 가능하다면 1을, 불가능하다면 0을 출력합니다.

입력

4 3 2
3 1
3 4
4 2
1 2

출력

1

제출 코드

def find(x):
    if parent[x] == x:
        return x
    parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    rootA = find(a)
    rootB = find(b)
    
    if rootA != rootB:
        parent[rootB] = rootA
        

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

parent = list(range(n+1))
rank = [0] * (n+1)

for i in range(m):
    a, b = map(int, input().split())
    union(a, b)
    
k_list = list(map(int,input().split()))

possible = True

for i in range(k-1):
    if find(k_list[i]) != find(k_list[i+1]):
        possible = False
        break

print(1 if possible else 0)