https://www.acmicpc.net/problem/6059

 

6059번: Pasture Walking

The N cows (2 <= N <= 1,000) conveniently numbered 1..N are grazing among the N pastures also conveniently numbered 1..N. Most conveniently of all, cow i is grazing in pasture i. Some pairs of pastures are connected by one of N-1 bidirectional walkways tha

www.acmicpc.net

문제는 영어로 되어있지만 lca 알고리즘을 응용해볼 수 있는 문제입니다.

요약하자면 구성된 트리에서 임의의 2개의 노드 간의 거리를 출력하는 문제입니다.

 

parent를 구할때 그 parent까지 가는 거리도 같이 구해줍니다.

 

이 풀이로 풀 수 있는 문제로는 icpc.me/1761 (정점들의 거리)가 있습니다.

 

 

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
#include <iostream>
#include <vector>
#define MAX 1000
#define LOG 11
using namespace std;
 
vector<pair<intint> > graph[MAX + 1];
pair<intint> parent[MAX + 1][LOG];
int depth[MAX + 1];
int N, M;
 
void dfs(int v, int d) {
    depth[v] = d;
 
    for (int i = 0; i < graph[v].size(); i++) {
        int next = graph[v][i].first;
        int w = graph[v][i].second;
 
        if (depth[next]) continue;
        parent[next][0= { v, w };
        dfs(next, d + 1);
    }
}
 
int lca(int u, int v) {
    int ans = 0;
    if (depth[u] > depth[v]) swap(u, v);
 
    for (int i = LOG - 1; i >= 0; i--) {
        if (depth[v] - depth[u] >= (1 << i)) {
            ans += parent[v][i].second;
            v = parent[v][i].first;
        }
    }
    if (u == v) return ans;
 
    for (int i = LOG - 1; i >= 0; i--) {
        if (parent[u][i].first != parent[v][i].first) {
            ans += (parent[u][i].second + parent[v][i].second);
            u = parent[u][i].first;
            v = parent[v][i].first;
        }
    }
 
    return ans + (parent[u][0].second + parent[v][0].second);
}
 
void func() {
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i <= N; i++) {
            parent[i][j].first = parent[parent[i][j - 1].first][j - 1].first;
            if (!parent[i][j].first) continue;
            parent[i][j].second = parent[i][j - 1].second + parent[parent[i][j - 1].first][j - 1].second;
        }
    }
 
    int u, v;
    while (M--) {
        cin >> u >> v;
        cout << lca(u, v) << '\n';
    }
}
 
void input() {
    int u, v, w;
    cin >> N >> M;
    for (int i = 0; i < N - 1; i++) {
        cin >> u >> v >> w;
        graph[u].push_back({ v,w });
        graph[v].push_back({ u,w });
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    dfs(11);
    func();
 
    return 0;
}
cs

'algorithm > LCA' 카테고리의 다른 글

boj 3584 가장 가까운 공통 조상  (0) 2021.06.16
boj 1626 두 번째로 작은 스패닝 트리  (0) 2021.04.02
boj 15481 그래프와 MST  (0) 2021.04.01
boj 15480 LCA와 쿼리  (0) 2021.02.14
boj 11438 LCA 2  (0) 2021.02.11

https://www.acmicpc.net/problem/3584

 

3584번: 가장 가까운 공통 조상

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두

www.acmicpc.net

LCA 알고리즘을 연습해볼 수 있는 간단한 문제입니다.

다만 이 문제는 방향 그래프이고, 루트가 정해져 있습니다.

 

저는 루트 확인을 chk 배열로 확인하였고, 입력이 자식으로 들어오지 않은 노드를 루트로 지정해주었습니다.

그리고 구했던 root를 시작으로 dfs를 돌려 각 노드의 depth를 구해주면서 자신들의 부모노드를 저장해줍니다. (parent[next][0] = v)

 

이제 자신의 2^n번째 조상을 모두 구하여 lca알고리즘으로 가장 가까운 공통 조상을 출력해줍니다.

 

이 문제는 입력이 10000개이므로 lca를 사용하지 않아도 풀리는 문제입니다.

자신의 부모만 구하여 최소 공통 조상을 구하는 방법인데 u, v의 높이를 같게 맞춘 다음 부모가 같아질때까지 한칸씩 위로 올리는 방식입니다.

소스 같이 올리겠습니다.

 

이 문제는 입력 범위가 작아서 그런지 시간은 동일하게 나왔습니다.

 

 

[LCA 사용]

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
#include <iostream>
#include <vector>
#include <cstring>
#define MAX 10000
#define LOG 15
using namespace std;
 
vector<int> graph[MAX + 1];
bool chk[MAX + 1];
int depth[MAX + 1];
int parent[MAX + 1][LOG];
int N, s, e, root;
 
void dfs(int v, int d) {
    depth[v] = d;
 
    for (int i = 0; i < graph[v].size(); i++) {
        int next = graph[v][i];
        
        if (depth[next]) continue;
        parent[next][0= v;
        dfs(next, d + 1);
    }
}
 
int lca(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
 
    for (int i = LOG - 1; i >= 0; i--) {
        if (depth[v] - depth[u] >= (1 << i)) {
            v = parent[v][i];
        }
    }
    if (u == v) return u;
 
    for (int i = LOG - 1; i >= 0; i--) {
        if (parent[u][i] != parent[v][i]) {
            u = parent[u][i];
            v = parent[v][i];
        }
    }
 
    return parent[v][0];
}
 
void func() {
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i <= N; i++) {
            parent[i][j] = parent[parent[i][j - 1]][j - 1];
        }
    }
 
    cout << lca(s, e) << '\n';
}
 
void input() {
    int u, v;
    cin >> N;
    for (int i = 0; i < N - 1; i++) {
        cin >> u >> v;
        graph[u].push_back(v);
        chk[v] = true;
    }
 
    for (int i = 1; i <= N; i++) {
        if (!chk[i]) {
            root = i;
            break;
        }
    }
 
    cin >> s >> e;
}
 
void init() {
    memset(depth, 0sizeof(depth));
    memset(parent, 0sizeof(parent));
    memset(chk, falsesizeof(chk));
    for (int i = 1; i <= N; i++) graph[i].clear();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        dfs(root, 1);
        func();
        init();
    }
 
    return 0;
}
cs

 

 

[LCA 사용X]

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
#include <iostream>
#include <vector>
#include <cstring>
#define MAX 10000
using namespace std;
 
vector<int> graph[MAX + 1];
bool chk[MAX + 1];
int depth[MAX + 1];
int parent[MAX + 1];
int N, s, e, root;
 
void dfs(int v, int d) {
    depth[v] = d;
 
    for (int i = 0; i < graph[v].size(); i++) {
        int next = graph[v][i];
        
        if (depth[next]) continue;
        parent[next] = v;
        dfs(next, d + 1);
    }
}
 
int func(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
 
    while (depth[u] != depth[v]) {
        v = parent[v];
    }
 
    if (u == v) return u;
 
    while (parent[u] != parent[v]) {
        u = parent[u];
        v = parent[v];
    }
 
    return parent[u];
}
 
void input() {
    int u, v;
    cin >> N;
    for (int i = 0; i < N - 1; i++) {
        cin >> u >> v;
        graph[u].push_back(v);
        chk[v] = true;
    }
 
    for (int i = 1; i <= N; i++) {
        if (!chk[i]) {
            root = i;
            break;
        }
    }
 
    cin >> s >> e;
}
 
void init() {
    memset(depth, 0sizeof(depth));
    memset(parent, 0sizeof(parent));
    memset(chk, falsesizeof(chk));
    for (int i = 1; i <= N; i++) graph[i].clear();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        dfs(root, 1);
        cout << func(s, e) << '\n';
        init();
    }
 
    return 0;
}
cs

'algorithm > LCA' 카테고리의 다른 글

boj 6059 Pasture Walking  (0) 2021.06.16
boj 1626 두 번째로 작은 스패닝 트리  (0) 2021.04.02
boj 15481 그래프와 MST  (0) 2021.04.01
boj 15480 LCA와 쿼리  (0) 2021.02.14
boj 11438 LCA 2  (0) 2021.02.11

www.acmicpc.net/problem/1626

 

1626번: 두 번째로 작은 스패닝 트리

첫째 줄에 그래프의 정점의 수 V(1 ≤ V ≤ 50,000)와 간선의 수 E(1 ≤ E ≤ 200,000)가 들어온다. 둘째 줄부터 E+1번째 줄까지 한 간선으로 연결된 두 정점과 그 간선의 가중치가 주어진다. 가중치는 100,

www.acmicpc.net

생애 첫 다이아문제 AC라 기분이 좋군요 ㅎㅎ

 

emoney96.tistory.com/193

 

boj 15481 그래프와 MST

www.acmicpc.net/problem/15481 15481번: 그래프와 MST 첫째 줄에 정점의 개수 N과 간선의 개수 M (2 ≤ N ≤ 200,000, N-1 ≤ M ≤ 200,000) 둘째 줄부터 M개의 줄에 간선의 정보 u, v, w가 주어진다. u와 v를..

emoney96.tistory.com

이 문제를 풀기 전에 그래프와 MST 문제를 풀어봐야합니다. (풀이가 비슷합니다.)

 

 

두 번째로 작은 스패닝 트리는 최소 스패닝 트리에서 하나의 간선만 바꿔주면 됩니다.

즉, 하나의 간선이 다릅니다.

 

1. 먼저 주어진 간선들로 첫 번째 mst를 구합니다.

2. 첫 번째 mst에 사용된 간선들로 인접 리스트를 만듭니다.

3. 인접 리스트의 depth를 구합니다.

4. 간선정보를 하나씩 가져와서 lca를 각각 구합니다.

5. mst - lca(u, v) + w의 최소를 구합니다.

 

여기까지는 그래프와 MST문제와 별다를게 없지만 이문제와의 차이점이 있습니다.

1. 두 번째 mst가 첫 번째 mst보다 커야함 -> 두 번째 mst를 구하지 못할 수 있음

2. 첫 번째 mst조차 구하지 못할 수 있음

 

위의 경우에는 -1을 출력해야합니다.

 

2번 경우를 확인할 때는 첫 번째 mst를 구할 때 고른 간선이 N - 1개인지 확인하는 것으로 예외처리 합니다.

1번 경우를 확인할 때는 lca로 u ~ v 경로의 간선을 구할 때

두개의 간선(가장 높은 가중치의 간선과 그 다음 높은 가중치의 간선)을 구합니다.

가장 높은 간선이 추가할 간선과 가중치가 같으면 1번조건에 걸리기 때문에 그 다음 높은 간선을 제거해야합니다.

 

마지막으로 ans가 최댓값이면 -1, 아니면 갱신된 값을 출력해줍니다.

 

정리하자면

1. 주어진 간선들로 첫 번째 mst를 구합니다.

2. 첫 번째 mst에 사용된 간선들로 인접 리스트를 만듭니다.

3. 인접 리스트의 depth를 구합니다.

4. lca(u, v)로 첫 번째, 두 번째 간선을 구합니다.

5. 구한 간선들이 w와 다를 경우에만 ans를 갱신합니다.

6. ans가 max값이면 -1, 아니면 갱신된 값을 출력합니다.

 

 

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define MAX 50000
#define LOG 20
using namespace std;
 
typedef struct edge {
    int u;
    int v;
    int w;
}edge;
 
vector<pair<intint> > list[MAX + 1];
vector<edge> v;
pair<intpair<intint> > lcaParent[MAX + 1][LOG];
int mstParent[MAX + 1], depth[MAX + 1];
bool visit[MAX + 1];
int mst;
int N, M, cnt;
 
bool cmp(edge a, edge b) {
    return a.w < b.w;
}
 
pair<intint> f(pair<intint> a, pair<intint> b) {
    vector<int> nv;
    nv.push_back(a.first);
    nv.push_back(a.second);
    nv.push_back(b.first);
    nv.push_back(b.second);
    sort(nv.rbegin(), nv.rend());
    nv.erase(unique(nv.begin(), nv.end()), nv.end());
    if (nv.size() < 2) nv.push_back(-1);
    return { nv[0], nv[1] };
}
 
void dfs(int v, int d) {
    depth[v] = d;
    visit[v] = true;
 
    for (int i = 0; i < list[v].size(); i++) {
        int next = list[v][i].first;
        int w = list[v][i].second;
 
        if (visit[next]) continue;
        lcaParent[next][0= { v,{w,-1} };
        dfs(next, d + 1);
    }
}
 
int find(int v) {
    if (mstParent[v] == v) return v;
    return mstParent[v] = find(mstParent[v]);
}
 
void Union(int x, int y, int w) {
    int a = find(x);
    int b = find(y);
 
    if (a == b) return;
    list[x].push_back({ y,w });
    list[y].push_back({ x,w });
    mstParent[b] = a;
    mst += w;
    cnt++;
}
 
void makeMst() {
    for (int i = 0; i < M; i++) {
        int x = v[i].u;
        int y = v[i].v;
        int w = v[i].w;
 
        Union(x, y, w);
        if (cnt == N - 1break;
    }
}
 
void init() {
    for (int i = 1; i <= N; i++) {
        mstParent[i] = i;
    }
    memset(lcaParent, -1sizeof(lcaParent));
}
 
pair<intint> lca(int x, int y) {
    if (depth[x] > depth[y]) swap(x, y);
    pair<intint> ret = { -1,-1 };
 
    for (int i = LOG - 1; i >= 0; i--) {
        if (depth[y] - depth[x] >= (1 << i)) {
            ret = f(ret, lcaParent[y][i].second);
            
            y = lcaParent[y][i].first;
        }
    }
 
    if (x == y) return ret;
 
    for (int i = LOG - 1; i >= 0; i--) {
        if (lcaParent[x][i].first == 0continue;
        if (lcaParent[x][i].first != lcaParent[y][i].first) {
            ret = f(ret, lcaParent[x][i].second);
            ret = f(ret, lcaParent[y][i].second);
 
            x = lcaParent[x][i].first;
            y = lcaParent[y][i].first;
        }
    }
 
    ret = f(ret, lcaParent[x][0].second);
    ret = f(ret, lcaParent[y][0].second);
    
    return ret;
}
 
void func() {
    if (cnt < N - 1) {
        cout << "-1\n";
        return;
    }
 
    dfs(11);
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i <= N; i++) {
            lcaParent[i][j].first = lcaParent[lcaParent[i][j - 1].first][j - 1].first;
            if (lcaParent[i][j].first == -1continue;
            lcaParent[i][j].second = f(lcaParent[i][j - 1].second, lcaParent[lcaParent[i][j - 1].first][j - 1].second);
        }
    }
 
    long long ans = 2147483647;
    for (int i = 0; i < M; i++) {
        int x = v[i].u;
        int y = v[i].v;
        int w = v[i].w;
        pair<intint> sub = lca(x, y);
        
        if (sub.first != w && sub.first != -1) ans = min(ans, (long long)(mst - sub.first + w));
        else if (sub.second != w && sub.second != -1) ans = min(ans, (long long)(mst - sub.second + w));
    }
 
    if (ans >= 2147483647cout << "-1\n";
    else cout << ans << '\n';
}
 
void input() {
    int x, y;
    int w;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> x >> y >> w;
        v.push_back({ x,y,w });
    }
    sort(v.begin(), v.end(), cmp);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    init();
    makeMst();
    func();
 
    return 0;
}
cs

'algorithm > LCA' 카테고리의 다른 글

boj 6059 Pasture Walking  (0) 2021.06.16
boj 3584 가장 가까운 공통 조상  (0) 2021.06.16
boj 15481 그래프와 MST  (0) 2021.04.01
boj 15480 LCA와 쿼리  (0) 2021.02.14
boj 11438 LCA 2  (0) 2021.02.11

www.acmicpc.net/problem/15481

 

15481번: 그래프와 MST

첫째 줄에 정점의 개수 N과 간선의 개수 M (2 ≤ N ≤ 200,000, N-1 ≤ M ≤ 200,000) 둘째 줄부터 M개의 줄에 간선의 정보 u, v, w가 주어진다. u와 v를 연결하는 간선의 가중치가 w라는 뜻이다. (1 ≤ u, v ≤

www.acmicpc.net

M개의 간선 정보가 들어오는데 i번째 간선을 포함한 MST를 출력하는 문제입니다.

 

우선 전체 MST를 구해줍니다.

그 다음 i번째 간선을 포함해주고 그 간선에 연결된 정점들의 경로에 있는 MST 간선을 하나 제거해야합니다.

이 경로를 순회해야 하기때문에 이를 LCA로 구합니다.

 

여기서 LCA를 구하기 전에 각 정점의 높이를 구해야하는데 인접 리스트를 MST 간선들만 가지고 구해줍니다.

그럼 u v 경로의 최대 간선을 구할 수 있습니다.

 

답은 mst - lca(u, v) + w을 출력해주시면 되고, 입력이 들어온 순서대로 출력해야하니 인덱스를 유지해야합니다.

 

정리하자면

1. 먼저 주어진 간선들로 MST를 구합니다.

2. MST에 사용된 간선들로 인접 리스트를 만들어줍니다.

3. 인접리스트의 depth를 구합니다.

4. 입력(간선 정보)이 들어왔던 순서대로 lca를 구해줍니다.

5. mst - lca(u, v) + w을 출력합니다.

 

 

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
133
134
135
136
137
138
139
140
141
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 200000
#define LOG 20
using namespace std;
typedef long long ll;
 
typedef struct edge {
    int u;
    int v;
    ll w;
}edge;
 
vector<pair<int, ll> > list[MAX + 1];
vector<edge> v, nv;
pair<int, ll> lcaParent[MAX + 1][LOG];
int mstParent[MAX + 1], depth[MAX + 1];
bool visit[MAX + 1];
ll mst;
int N, M, cnt;
 
bool cmp(edge a, edge b) {
    return a.w < b.w;
}
 
void dfs(int v, int d) {
    depth[v] = d;
    visit[v] = true;
 
    for (int i = 0; i < list[v].size(); i++) {
        int next = list[v][i].first;
        ll w = list[v][i].second;
 
        if (visit[next]) continue;
        lcaParent[next][0= { v,w };
        dfs(next, d + 1);
    }
}
 
int find(int v) {
    if (mstParent[v] == v) return v;
    return mstParent[v] = find(mstParent[v]);
}
 
void Union(int x, int y, ll w) {
    int a = find(x);
    int b = find(y);
 
    if (a == b) return;
    list[x].push_back({ y,w });
    list[y].push_back({ x,w });
    mstParent[b] = a;
    mst += w;
    cnt++;
}
 
void makeMst() {
    for (int i = 0; i < M; i++) {
        int x = nv[i].u;
        int y = nv[i].v;
        ll w = nv[i].w;
 
        Union(x, y, w);
        if (cnt == N - 1break;
    }
}
 
void init() {
    for (int i = 1; i <= N; i++) {
        mstParent[i] = i;
    }
}
 
ll lca(int x, int y) {
    if (depth[x] > depth[y]) swap(x, y);
    ll ret = 0;
 
    for (int i = LOG - 1; i >= 0; i--) {
        if (depth[y] - depth[x] >= (1 << i)) {
            ret = max(ret, lcaParent[y][i].second);
            y = lcaParent[y][i].first;
        }
    }
 
    if (x == y) return ret;
 
    for (int i = LOG - 1; i >= 0; i--) {
        if (lcaParent[x][i].first == 0continue;
        if (lcaParent[x][i].first != lcaParent[y][i].first) {
            ret = max(ret, max(lcaParent[x][i].second, lcaParent[y][i].second));
 
            x = lcaParent[x][i].first;
            y = lcaParent[y][i].first;
        }
    }
 
    return max(ret, max(lcaParent[x][0].second, lcaParent[y][0].second));
}
 
void func() {
    dfs(11);
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i <= N; i++) {
            lcaParent[i][j].first = lcaParent[lcaParent[i][j - 1].first][j - 1].first;
            lcaParent[i][j].second = max(lcaParent[i][j - 1].second, lcaParent[lcaParent[i][j - 1].first][j - 1].second);
        }
    }
 
    for (int i = 0; i < M; i++) {
        int x = v[i].u;
        int y = v[i].v;
        ll w = v[i].w;
        ll sub = lca(x, y);
        cout << mst - sub + w << '\n';
    }
}
 
void input() {
    int x, y;
    ll w;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> x >> y >> w;
        v.push_back({ x,y,w });
    }
    nv = v;
    sort(nv.begin(), nv.end(), cmp);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    init();
    makeMst();
    func();
 
    return 0;
}
cs

'algorithm > LCA' 카테고리의 다른 글

boj 3584 가장 가까운 공통 조상  (0) 2021.06.16
boj 1626 두 번째로 작은 스패닝 트리  (0) 2021.04.02
boj 15480 LCA와 쿼리  (0) 2021.02.14
boj 11438 LCA 2  (0) 2021.02.11
boj 11437 LCA  (0) 2021.02.11

www.acmicpc.net/problem/15480

 

15480번: LCA와 쿼리

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리 T의 간선 정보 u와 v가 주어지다. u와 v는 트리의 간선을 나타내는 두 정점이다. 다음 줄에는 쿼리의 개수 M(

www.acmicpc.net

먼저 트리의 구조가 주어지고 쿼리가 r u v 형식으로 주어집니다.

r u v는 루트가 r일 때 u와 v의 LCA를 출력해야합니다.

 

루트가 r일 때 u와 v의 LCA는

r, u의 lca노드의 depth

r, v의 lca노드의 depth

u, v의 lca노드의 depth

중 가장 큰 depth를 가진 노드가 정답이 됩니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<Integer> list[];
    static boolean visit[];
    static int parent[][] = new int[100001][21];
    static int depth[];
    static int N, M;
 
    static void dfs(int v, int d) {
        depth[v] = d;
        visit[v] = true;
 
        for (int i = 0; i < list[v].size(); i++) {
            int next = list[v].get(i);
 
            if (visit[next])
                continue;
            parent[next][0= v;
            dfs(next, d + 1);
        }
    }
 
    static void func() {
        dfs(11);
        for (int j = 1; j < 21; j++) {
            for (int i = 1; i <= N; i++) {
                parent[i][j] = parent[parent[i][j - 1]][j - 1];
            }
        }
    }
 
    static int lca(int x, int y) {
        if (depth[x] > depth[y]) {
            int tmp = x;
            x = y;
            y = tmp;
        }
 
        for (int i = 20; i >= 0; i--) {
            if (depth[y] - depth[x] >= (1 << i)) {
                y = parent[y][i];
            }
        }
 
        if (x == y)
            return x;
 
        for (int i = 20; i >= 0; i--) {
            if (parent[x][i] != parent[y][i]) {
                x = parent[x][i];
                y = parent[y][i];
            }
        }
 
        return parent[x][0];
    }
 
    static void solve() throws Exception {
        StringBuffer sb = new StringBuffer();
        int r, u, v;
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            r = Integer.parseInt(st.nextToken());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
 
            int a = lca(r, u);
            int b = lca(r, v);
            int c = lca(u, v);
            int ans = depth[a] > depth[b] ? (depth[a] > depth[c] ? a : c) : (depth[b] > depth[c] ? b : c);
 
            sb.append(ans + "\n");
        }
 
        System.out.print(sb.toString());
    }
 
    static void input() throws Exception {
        int u, v;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        depth = new int[N + 1];
        visit = new boolean[N + 1];
        list = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++)
            list[i] = new ArrayList<>();
 
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
 
            list[u].add(v);
            list[v].add(u);
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        solve();
    }
}
cs

'algorithm > LCA' 카테고리의 다른 글

boj 1626 두 번째로 작은 스패닝 트리  (0) 2021.04.02
boj 15481 그래프와 MST  (0) 2021.04.01
boj 11438 LCA 2  (0) 2021.02.11
boj 11437 LCA  (0) 2021.02.11
boj 13116 30번  (0) 2021.02.09

www.acmicpc.net/problem/11437

 

11437번: LCA

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정

www.acmicpc.net

 

 

LCA 알고리즘으로 해결하였습니다.

 

정점이 N개이고, N - 1개의 간선정보가 입력주어 주어집니다.

u와 v를 서로 연결시켜주고 루트노드인 1부터 dfs를 돌려서 각 노드의 높이를 먼저 구해줍니다.

높이를 구하는 과정에서 자식노드가 next로 나오는데 next의 첫번째 조상노드를 v로 저장해둡니다.

 

dfs순회가 끝나면 이제 각 노드의 2^N번째 조상노드를 저장해줍니다.

첫번째 조상노드부터 차례대로 저장하여 순회하면 시간적으로 비효율적이고,

1, 2, 4, 8, ~ 2^N번째 조상노드만 저장해줘도 모든 조상노드를 탐색할 수 있습니다.

 

그리고 u, v 정점이 입력으로 들어오면 lca함수를 통해 최소 공통 조상노드를 구해줍니다.

먼저 노드의 depth가 높은쪽을 y에 맞춘 후에 y노드의 높이를 x와 같게 맞춰줍니다.

그 다음 x와 y의 조상이 같아질때까지 올라가주면 됩니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static ArrayList<Integer> list[] = new ArrayList[50001];
    static boolean visit[];
    static int parent[][] = new int[50001][17];
    static int depth[] = new int[50001];
    static int N, M;
 
    static void dfs(int v, int d) {
        visit[v] = true;
        depth[v] = d;
 
        for (int i = 0; i < list[v].size(); i++) {
            int next = list[v].get(i);
 
            if (visit[next])
                continue;
 
            parent[next][0= v;
            dfs(next, d + 1);
        }
    }
 
    static void func() {
        dfs(11);
        for (int j = 1; j < 17; j++) {
            for (int i = 1; i <= N; i++) {
                parent[i][j] = parent[parent[i][j - 1]][j - 1];
            }
        }
    }
 
    static int lca(int x, int y) {
        if (depth[x] > depth[y]) {
            int tmp = x;
            x = y;
            y = tmp;
        }
 
        for (int i = 16; i >= 0; i--) {
            if (depth[y] - depth[x] >= (1 << i)) {
                y = parent[y][i];
            }
        }
 
        if (y == x)
            return x;
 
        for (int i = 16; i >= 0; i--) {
            if (parent[x][i] != parent[y][i]) {
                x = parent[x][i];
                y = parent[y][i];
            }
        }
 
        return parent[x][0];
    }
 
    static void solve() throws Exception {
        int u, v;
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            sb.append(lca(u, v) + "\n");
        }
        
        System.out.print(sb.toString());
    }
 
    static void input() throws Exception {
        int u, v;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        visit = new boolean[N + 1];
        for (int i = 1; i <= N; i++)
            list[i] = new ArrayList<>();
 
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            list[u].add(v);
            list[v].add(u);
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        solve();
    }
}
cs

'algorithm > LCA' 카테고리의 다른 글

boj 1626 두 번째로 작은 스패닝 트리  (0) 2021.04.02
boj 15481 그래프와 MST  (0) 2021.04.01
boj 15480 LCA와 쿼리  (0) 2021.02.14
boj 11438 LCA 2  (0) 2021.02.11
boj 13116 30번  (0) 2021.02.09

www.acmicpc.net/problem/13116

 

13116번: 30번

첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 50 000)가 주어진다. 이후 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 구성되어 있으며, 각 줄에는 두 개의 정수 A와 B (1 ≤ A, B ≤ 1

www.acmicpc.net

사실 링크없이 이문제만 올려놔도 될 정도입니다..

위의 사진처럼 1 ~ 1023까지 perfect binary tree를 구성하고 있습니다.

여기서 a와 b의 최소 공통조상노드를 구하는 문제입니다.

 

트리는 고정이기때문에 depth와 parent는 입력을 받기전에 미리 구성해줍니다.

우선 dfs로 탐색을 진행하여 노드의 깊이를 저장해줍니다.

dfs로 탐색을 진행하면서 parent[v][0]에 부모노드인 v / 2를 저장합니다.

그 다음 parent배열에 자신의 1, 2, 4, 8, ... (2^N)번째 조상노드를 저장합니다.

 

입력으로 x, y를 받으면 x와 y의 최소 공통조상노드를 구합니다.

우선 y의 깊이가 더 크게 맞춰놓고

y의 깊이를 x에 맞춰줍니다.

 

그 다음 x와 y의 조상이 같아질때까지

x = parent[x][i]

y = parent[y][i]

연산을 반복합니다.

 

최종적으로 parent[x][0]을 출력해줍니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static int depth[] = new int[1024];
    static int parent[][] = new int[1024][11];
 
    static void dfs(int v, int d) {
        depth[v] = d;
        parent[v][0= v / 2;
 
        int next = v * 2;
 
        if (next >= 1024)
            return;
 
        dfs(next, d + 1);
        dfs(next + 1, d + 1);
    }
 
    static void init() {
        dfs(11);
        for (int j = 1; j < 11; j++) {
            for (int i = 1; i <= 1023; i++) {
                parent[i][j] = parent[parent[i][j - 1]][j - 1];
            }
        }
    }
 
    static int lca(int x, int y) {
        if (depth[x] > depth[y]) {
            int tmp = x;
            x = y;
            y = tmp;
        }
 
        for (int i = 10; i >= 0; i--) {
            if (depth[y] - depth[x] >= (1 << i)) {
                y = parent[y][i];
            }
        }
 
        if (x == y)
            return x;
 
        for (int i = 10; i >= 0; i--) {
            if (parent[x][i] != parent[y][i]) {
                x = parent[x][i];
                y = parent[y][i];
            }
        }
        
        return parent[x][0];
    }
 
    static void input() throws Exception {
        int u, v;
        st = new StringTokenizer(br.readLine());
        u = Integer.parseInt(st.nextToken());
        v = Integer.parseInt(st.nextToken());
 
        sb.append(lca(u, v) * 10 + "\n");
    }
 
    public static void main(String[] args) throws Exception {
        init();
        st = new StringTokenizer(br.readLine());
        int tc = Integer.parseInt(st.nextToken());
        while (tc-- > 0) {
            input();
        }
        
        System.out.println(sb.toString());
    }
}
cs

'algorithm > LCA' 카테고리의 다른 글

boj 1626 두 번째로 작은 스패닝 트리  (0) 2021.04.02
boj 15481 그래프와 MST  (0) 2021.04.01
boj 15480 LCA와 쿼리  (0) 2021.02.14
boj 11438 LCA 2  (0) 2021.02.11
boj 11437 LCA  (0) 2021.02.11

+ Recent posts