[IZhO] 2013 Day 1 D번 - 특수한 그래프
oj.uz 링크그래프적 풀이 서로 어떤 방향으로든 연결된 정점 덩어리(component)를 하나 잡는다고 하자. 정점이 N개인 덩어리에는 간선이 N개 있다. 잘 생각해보면 이 컴포넌트에는 반드시 한 개의 사이클이 존재하고, 유일하다. 그럼, 또다시 생각해보면 이 컴포넌트는 한 개의 사이클에 여러 정점이 매달린 모습이다.또한 사이클에 속해있는 점들은, 자신에게 매달린 점들과 그 밑의 점들을 모두 생각한 하나의 트리의 루트이다.그렇다면 이제 답변을 간단하게 할 수 있다. 서로 다른 component에 속해있는 점들은 -1을 찍으면 된다. 한 component에 속해있는 경우, 두 점이 같은 트리에 속해있다면, 서로 부모-자식 관계일 때만 만날 수 있다. 두 점이 다른 트리에 속해있다면, 사이클 상에서 각각의..
2016. 1. 8. 09:19