[이코테] CH10 그래프 이론 실전문제 42번 탑승구

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9
def find_parent(parent,x):
    if parent[x]!=x:
        parent[x] = find_parent(parent,parent[x])
    return parent[x]

def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

G = int(input())
P = int(input())
sum = 0
parent = [0] *(G+1)
for i in range(1,G+1):
    parent[i] = i
for _ in range(P):
    value = find_parent(parent,int(input()))
    if value == 0:
        break
    union_parent(parent,value,value-1) # 바로 왼쪽 집합과 비교하기 위해서
    sum +=1
print(sum)

서로소를 이용해야 하는 것 같긴 했는데....... 아무리봐도 모르겠어서 그냥 답지 봤다

근데 이건 며칠 고민했어도 못 풀었을듯

0번째 탑승구가 있다면 취소하는 방향이라니..

바로 왼쪽 집합과 비교해서 루트 노드가 0이 아니라면 연결할 수 있다는 의미이고

루트 노드가 0이라면 더이상 자리가 없다는 소리..

어렵다.

2회독때 다시 풀땐 이 아이디어를 떠올릴수라도 있으면 좋겠다