[IZhO] 2013 Day 1 D번 - 특수한 그래프

oj.uz 링크

그래프적 풀이

서로 어떤 방향으로든 연결된 정점 덩어리(component)를 하나 잡는다고 하자.
정점이 N개인 덩어리에는 간선이 N개 있다.
잘 생각해보면 이 컴포넌트에는 반드시 한 개의 사이클이 존재하고, 유일하다.
그럼, 또다시 생각해보면 이 컴포넌트는 한 개의 사이클에 여러 정점이 매달린 모습이다.

또한 사이클에 속해있는 점들은, 자신에게 매달린 점들과 그 밑의 점들을 모두 생각한 하나의 트리의 루트이다.

그렇다면 이제 답변을 간단하게 할 수 있다.
서로 다른 component에 속해있는 점들은 -1을 찍으면 된다.
한 component에 속해있는 경우, 두 점이 같은 트리에 속해있다면, 서로 부모-자식 관계일 때만 만날 수 있다.
두 점이 다른 트리에 속해있다면, 사이클 상에서 각각의 루트 사이의 거리와, 각 점에서 루트까지 올라가는 거리를 더해주면 된다.

그런데 간선을 제거하는 것은 어떻게 할까?

우리가 확인해야 하는 것은, 부모-자식 관계의 두 점이 연결되어있는가와, 한 정점에서 루트까지가 연결되어있는가, 그리고 사이클 상에서의 연결관계이다.

앞의 두 개는 트리 상에서 확인하는 것이므로 Heavy-Light Decomposition을 이용하여 수행할 수 있다.
사이클 상에서의 연결관계는 어떻게 확인할 수 있을까?
사이클은 시간이 지날 수록 조각날 것이다. 그렇다면 조각난 사이클에서 시작해, 시간을 거꾸로 가며 Union-Find를 수행하여 두 정점이 같은 사이클 조각에 포함되어있는지를 검사하면 된다.

Link-Cut Tree 풀이

한 컴포넌트를, 모든 원소가 부모를 가리키고 루트가 특정 원소를 가리키고 있는 트리로 생각할 수 있다.
Link-cut Tree를 사용하면 된다.