예비 정비팀

이미 투입된 역만 남긴 유도 부분 그래프를 생각하자. 원래 그래프가 트리이므로 이 그래프의 연결 요소는 서로소 집합 자료 구조로 관리할 수 있다. 경로 $P(u,v)$에 대기 중인 팀이 없다는 것은 $u$와 $v$가 투입된 역만으로 같은 연결 요소에 속한다는 것과 동치이다.

등록된 각 경로의 두 끝 연결 요소 사이에 금지 간선을 둔다. 역 $x$를 투입하면 $x$와 이미 투입된 이웃들의 연결 요소가 합쳐진다. 합쳐지는 연결 요소 사이에 금지 간선이 있으면 기존 경로가 비게 된다. 새 경로의 두 끝점이 합친 뒤 같은 연결 요소가 되는지도 확인한다.

각 연결 요소가 인접한 금지 연결 요소의 집합을 저장하고 작은 집합을 큰 집합에 합친다. 각 공사에서 계획 $0$을 먼저 검사하면 우선순위 규칙도 만족한다.

Solution written by GPT5