문제 보기
입력이 너무 많아서 싱크를 끊지 않고서는 cin/cout 사용으로 해결할 수 없습니다.

핵심 아이디어

그리디한 생각으로 가봅시다!
위, 아래로 뻗어가면서 그래프를 그려 나가야 하나, 하는 생각도 했지만, 그럴 필요가 없다는 것을 깨달을 수 있습니다.
왜냐면 수직적으로 겹치는 구간에 있는 통나무끼리는 점프가 가능하기 때문입니다.

따라서 그리디라는 결론을 확인할 수 있습니다.
하지만, 매번 한 가지의 통나무로 이동하기 위해 같은 프로세스를 돌린다면 매우 비효율적으로 구현될 것입니다.
즉, 여태 수행해서 갈 수 있음이 확정된 통나무는 다시 확인을 하는 작업이 없어야 한다는 것입니다.
이를 위해 DSU가 필요합니다. (Disjoint Set Union a.k.a. Union-Find Data Structure)

구현

follow는 특정 Set을 이루고 있는 원소들의 수를 나타냅니다.
link는 원소가 속하는 Set의 대푯값으로 연결됩니다.
logs는 {(앞 좌표), (뒷 좌표), (인덱스)}로 구성됩니다.
find 함수와 unite 함수는 각각 경로 압축과 smaller to larger technique를 이용합니다.
중심이 되는 for문 안에서의 head는 시작하는 통나무를 가리킵니다. auto 키워드로 축약했습니다.

이해가 안 되시는 부분은 댓글로 남겨주세요~!