오프라인 쿼리11 백준 13306 자바 - 트리 (BOJ 13306 JAVA) [ 백준 13306 ] [ 코드 (깃헙) ] 트리의 부모를 알려주고, 주어진 쿼리를 해결하는 문제이다. 쿼리는 '0 b'와 같이 들어오면 b번째 edge 제거하는 쿼리와, '1 c d'와 같이 들어오면 c와 d 사이에 연결경로가 있는지 묻는 쿼리가 있다. 일단 거리 자체를 묻지 않고, 연결 경로가 있는지만 파악하면 된다. 그럼 이거엔 union-find 알고리즘을 쓰면 될 것임을 알 수 있다. 다만 해당 알고리즘의 경우 그룹간의 관계를 맺는것은 쉽지만, 연결을 끊는건 힘들다. 그럼 쿼리를 반대순서로 보면 어떻게 될까? 원래 순서대로라면 '간선들이 존재하는 그래프에서 edge를 제거하면서 중간중간 특정 노드간에 연결경로가 있는지 묻는 쿼리' 이지만, 반대로 미리 쿼리상에 존재하는 모든 간선을 제거한 후 역.. 2021. 11. 4. 이전 1 2 다음
