이미 투입된 역만 남긴 유도 부분 그래프를 생각하자. 원래 그래프가 트리이므로 이 그래프의 연결 요소는 서로소 집합 자료 구조로 관리할 수 있다. 경로 에 대기 중인 팀이 없다는 것은 와 가 투입된 역만으로 같은 연결 요소에 속한다는 것과 동치이다.
등록된 각 경로의 두 끝 연결 요소 사이에 금지 간선을 둔다. 역 를 투입하면 와 이미 투입된 이웃들의 연결 요소가 합쳐진다. 합쳐지는 연결 요소 사이에 금지 간선이 있으면 기존 경로가 비게 된다. 새 경로의 두 끝점이 합친 뒤 같은 연결 요소가 되는지도 확인한다.
각 연결 요소가 인접한 금지 연결 요소의 집합을 저장하고 작은 집합을 큰 집합에 합친다. 각 공사에서 계획 을 먼저 검사하면 우선순위 규칙도 만족한다.
Solution written by GPT5
