알고리즘 기술
LCA
헐랭미
2020. 8. 20. 11:55
https://www.acmicpc.net/problem/11438
11438번: LCA 2
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정�
www.acmicpc.net
이 기초다.
|
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
81
82
83
84
85
86
87
88
89
90
91
92
93
|
#include <iostream>
#include <vector>
#include <algorithm>
#define pii pair<int, int>
using namespace std;
int n;
vector<int> edge[100001];
int LCA[100001][18] = { 0 };
int depth[100001];
void go(int cur, int parent, int d)
{
LCA[cur][0] = parent;
depth[cur] = d;
for (int i = 1; i < 18; i++)
{
LCA[cur][i] = LCA[LCA[cur][i - 1]][i - 1];
}
for (int i = 0; i < edge[cur].size(); i++)
{
if (edge[cur][i] == parent)
continue;
go(edge[cur][i], cur, d+1);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n;
int a, b;
for (int i = 0; i < n-1; i++)
{
cin >> a >> b;
edge[a].push_back(b);
edge[b].push_back(a);
}
go(1, 0, 1);
/*
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < 18; j++)
cout << LCA[i][j] << ' ';
cout << '\n';
}
*/
int m;
cin >> m;
for (int i = 0; i < m; i++)
{
cin >> a >> b;
if (depth[a] > depth[b])
swap(a, b); // b가 무조건 더 깊다.
for (int i = 17; i >= 0; i--)
{
if (depth[LCA[b][i]] >= depth[a]) // 깊이 같게 맞춰주기.
b = LCA[b][i];
}
if (a == b)
cout << b << '\n';
else
{
for (int i = 17; i >= 0; i--)
{
int aa = LCA[a][i];
int bb = LCA[b][i];
if (aa == bb)
continue;
a = aa;
b = bb;
}
cout << LCA[a][0] << '\n';
}
}
}
|
cs |
그리고 밑에는 STL 없애고 푼것이다.
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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 | #include <iostream> using namespace std; int n; int LCA[100001][18] = { 0 }; int depth[100001]; class node { public : int data; node* next; }; class Edge { public : node* head = NULL; node* tail = NULL; void insert(int d) { node* nnode = new node; nnode->data = d; nnode->next = NULL; if (head == NULL) head = nnode; else tail->next = nnode; tail = nnode; } }; Edge edge[100001]; void go(int cur, int parent, int d) { LCA[cur][0] = parent; depth[cur] = d; for (int i = 1; i < 18; i++) { LCA[cur][i] = LCA[LCA[cur][i - 1]][i - 1]; } node* tmp = edge[cur].head; while (tmp != NULL) { if (tmp->data != parent) go(tmp->data, cur, d + 1); tmp = tmp->next; } /* for (int i = 0; i < edge[cur].size(); i++) { if (edge[cur][i] == parent) continue; go(edge[cur][i], cur, d + 1); } */ } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; int a, b; for (int i = 0; i < n - 1; i++) { cin >> a >> b; edge[a].insert(b); edge[b].insert(a); } go(1, 0, 1); /* for (int i = 1; i <= n; i++) { for (int j = 0; j < 18; j++) cout << LCA[i][j] << ' '; cout << '\n'; } */ int m; cin >> m; for (int i = 0; i < m; i++) { cin >> a >> b; if (depth[a] > depth[b]) swap(a, b); // b가 무조건 더 깊다. for (int i = 17; i >= 0; i--) { if (depth[LCA[b][i]] >= depth[a]) // 깊이 같게 맞춰주기. b = LCA[b][i]; } if (a == b) cout << b << '\n'; else { for (int i = 17; i >= 0; i--) { int aa = LCA[a][i]; int bb = LCA[b][i]; if (aa == bb) continue; a = aa; b = bb; } cout << LCA[a][0] << '\n'; } } } | cs |