아무 말

서론 그래프에서의 동형사상을 찾는 문제는 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는 모두 서로 다른 서브 트리에 존재할 수 있게 하는 정점. 이를 토대로 생각하면, 아무 노드나 잡..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 심플하게 위상 정렬을 수행하는 문제 위상 정렬에 대한 설명은 아래의 포스트를 참조 https://jiuge-meogari-ps.tistory.com/14 위상 정렬(Topological Sort) 위상 정렬(topological sort)은 G가 간선 (u,v)를 가질 때 u가 v보다 순서상으로 먼저 나타나도록 모든 정점을 선형으로 나열하는 것이다. 여기..

위상 정렬(topological sort)은 G가 간선 (u,v)를 가질 때 u가 v보다 순서상으로 먼저 나타나도록 모든 정점을 선형으로 나열하는 것이다. 여기서 만약 그래프가 순환을 가진다면 선형 나열은 불가능하다. 아래와 같은 알고리즘은 하나의 방향 비순환 그래프를 위상 정렬 한다. 위상 정렬(G) 1 각 정점 v에 대해 종료 시간 v.f를 계산하기 위해 DFS(G)를 호출한다. 2 각 정점이 종료될 때마다 연결 리스트의 맨 앞에 삽입한다. 3 return 정점의 연결 리스트 중요한것은 위상 정렬한 순서대로 일을 수행할 때 일을 수행하지 못하는 일이 나오지 않는다는 것이다. 미리 어떠한 행동 A를 해야 B를 할 수 있다면 A를 하고 B를 해야한다는 것이다. 위 방식으로 위상 정렬을 할 때 시간복잡도는..