아무 말

서론 그래프에서의 동형사상을 찾는 문제는 NP이다. 다만, 트리에서의 동형사상은 다항시간에 판정할 수 있다. 이번 포스팅에서는 두 rooted 트리에서의 동형사상을 찾는 알고리즘인 AHU Algorithm [Aho, Hopcroft and Ullman]과 unrooted tree의 동형사상을 찾는 방법을 다룰 것이다. 1. 동형인지 여부를 판정할 트리가 rooted tree 일 때 - AHU algorithm AHU algorithm에서는 트리를 몇 개의 튜플로 해싱하여 두 트리가 같은지 비교한다. 이때, depth 별로 tuple을 하나씩 형성해주어야 한다. 이 tuple을 이루는 항은 AHU algorithm에서는 각 depth별 vertex의 degree들이다. 또, tuple은 항상 정렬된 상태로..

보호되어 있는 글입니다.

https://www.acmicpc.net/problem/15480 15480번: LCA와 쿼리 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리 T의 간선 정보 u와 v가 주어지다. u와 v는 트리의 간선을 나타내는 두 정점이다. 다음 줄에는 쿼리의 개수 M( www.acmicpc.net 풀이를 위한 발상 한 정점을 루트로 하는 트리에서 다른 두 정점의 LCA를 찾아야 한다. 조금 생각을 해보면, 이때의 LCA는 세 정점의 접합점이라는 것을 알 수 있다. 조금 더 구체적으로 표현하자면 다음과 같다. 한 정점으로 트리를 분할했을 때, 정점 r, u, v는 모두 서로 다른 서브 트리에 존재할 수 있게 하는 정점. 이를 토대로 생각하면, 아무 노드나 잡..