트리(Tree)에서 특정한 두 노드의 공통된 조상 중에서 가장 가까운 조상
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
#define _CRT_SECURE_NO_WARNINGS
#define INF 987654321
#include <iostream>
#include <vector>
using namespace std;
vector<int> tree[1001];
const int DEPTH = 11; // 전체 노드의 갯수는 2^10개 이하
int node_num = 100; // 노드의 갯수
int parent[1001][DEPTH];
int d[1001];
int c[1001]; // 처리여부, 체크
void dfs(int s, int depth) {
c[s] = 1;
d[s] = depth;
for (int i = 0; i < tree[s].size(); i++) {
int next = tree[s][i];
if (c[next]) continue;
parent[next][0] = s;
dfs(next, depth + 1);
}
}
void getParent() {
dfs(0, 0); // 각 노드를 부모와 연결한다
for (int i = 1; i < DEPTH; i++) {
for (int j = 0; j < node_num; j++) {
parent[j][i] = parent[parent[j][i - 1]][i - 1]; // 각 노드의 부모 관계를 모두 찾아준다
}
}
}
int LCA(int x, int y) {
if (d[y] < d[x]) {
swap(x, y); // y가 더 깊도록 만든다.
}
// 두 노드의 깊이를 맞춰준다.
for (int i = DEPTH - 1; i >= 0; i--) {
if (d[y] - d[x] >= (1 << i)) {
y = parent[y][i];
}
}
if (x == y) return x; // 부모가 같은 경우
for (int i = DEPTH - 1; i >= 0; i--) {
if (parent[x][i] != parent[y][i]) {
x = parent[x][i];
y = parent[y][i];
}
}
return parent[x][0];
}
int main() {
return 0;
}
|
cs |
https://www.acmicpc.net/problem/11438
11438번: LCA 2
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정
www.acmicpc.net
https://www.acmicpc.net/problem/1761
1761번: 정점들의 거리
첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩
www.acmicpc.net
https://www.acmicpc.net/problem/8012
8012번: 한동이는 영업사원!
한동이는 경상도내를 돌아다니면서 열심히 일하는 영업사원이다. 예전에는 자기가 원하는 도시만 골라서 다닐 수 있었지만 시대가 바뀌어서 이제 그렇게는 하지 못하게 되었다. 시대가 바뀜에
www.acmicpc.net
반응형
'자료구조 + 알고리즘' 카테고리의 다른 글
| LCS (Longest Common Subsequence, 최장 공통 부분수열) (0) | 2021.09.14 |
|---|---|
| LIS (Longest Increasing Subsequence, 최장 증가 부분수열) (0) | 2021.09.14 |
| 문자열 매칭 알고리즘 (0) | 2021.09.14 |
| 최소비용 최대유량 알고리즘 (0) | 2021.09.14 |
| 이분매칭 (Bipartite Matching) (0) | 2021.09.14 |