728x90
0. [c++] 백준 - |
https://www.acmicpc.net/problem/3584
1. 풀이 |
1)
2)
3)
2. 소스코드 |
#include<iostream>
#include<vector>
using namespace std;
int T, N;
vector<vector<int> > V;
vector<int> parent;
vector<int> depth;
void dfs(const int& here, const int& dep) {
depth[here] = dep;
for (int i = 0; i < V[here].size(); i++) {
int there = V[here][i];
dfs(there, dep + 1);
}
}
int main() {
cin >> T;
while (T--) {
cin >> N;
//1번부터 N번까지 공간 할당
V.assign(N + 1, vector<int>());
parent.assign(N + 1, 0);
depth.assign(N + 1, 0);
//input data 처리
int u, v;
for (int i = 0; i < N - 1; i++) {
cin >> u >> v;
V[u].push_back(v);
parent[v] = u;
}
for (int i = 1; i <= N; i++) {
if (!parent[i]) {
parent[i] = i;
dfs(i, 1);
break;
}
}
cin >> u >> v;
while (depth[u] != depth[v]) {
if (depth[u] < depth[v]) {
v = parent[v];
}
else {
u = parent[u];
}
}
while (u != v) {
v = parent[v];
u = parent[u];
}
cout << v << endl;
}
}
3. 참고 |
질문이나 지적 있으시면 댓글로 남겨주세요~
도움 되셨으면 하트 꾹!
'<백준> > |c++| normal' 카테고리의 다른 글
[C++] 백준 10757 - 큰 수 A+B(문자열 덧셈, strlen) (0) | 2021.02.24 |
---|---|
[C++] 백준 17435 - 합성함수와 쿼리 (0) | 2020.11.27 |
[C++] 백준 10266 - 시계 사진(KMP 알고리즘, 문자열) (0) | 2020.09.11 |
[C++] 백준 14725 - 개미굴(문자열, 스택) (0) | 2020.09.11 |
[C++] 백준 2162 - 선분 그룹 (유니온 파인드, 계산 기하) (0) | 2020.09.07 |