득이공간
[백준 C++] 3584 가장 가까운 공통 조상 - 최소공통조상 본문
#include <iostream>
#include <list>
#include <queue>
using namespace std;
const int& MaxSize = 10001;
list<int> Children[MaxSize];
pair<int, int> Tree[MaxSize];
queue<int> SearchQueue;
void SearchLCA(int NodeA, int NodeB)
{
int A = NodeA;
int B = NodeB;
while (Tree[A].second != Tree[B].second)
{
if (Tree[A].second > Tree[B].second)
{
A = Tree[A].first;
}
else if (Tree[A].second < Tree[B].second)
{
B = Tree[B].first;
}
}
if (A == B)
{
cout << A << '\n';
return;
}
while (A != B)
{
A = Tree[A].first;
B = Tree[B].first;
}
cout << A << '\n';
}
void InitDepthInfo(int RootNode)
{
Tree[RootNode].second = 1;
SearchQueue.emplace(RootNode);
while (!SearchQueue.empty())
{
int Current = SearchQueue.front();
SearchQueue.pop();
for (const int& Child : Children[Current])
{
Tree[Child].second = Tree[Current].second + 1;
SearchQueue.emplace(Child);
}
}
}
void TestCase()
{
for (int i = 0; i < MaxSize; ++i)
{
Children[i].clear();
Tree[i] = pair<int, int>();
}
int N;
cin >> N;
for (int i = 0; i < N - 1; ++i)
{
int A, B;
cin >> A >> B;
Children[A].emplace_back(B);
Tree[B].first = A;
}
int RootNode = 0;
for (int i = 1; i <= N; ++i)
{
if (Tree[i].first == 0)
{
RootNode = i;
}
}
InitDepthInfo(RootNode);
int NodeA, NodeB;
cin >> NodeA >> NodeB;
SearchLCA(NodeA, NodeB);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
for (int i = 0; i < T; ++i)
{
TestCase();
}
}
11437(LCA) 문제와 동일하게 최소 공통 조상 노드를 구하는 문제입니다.
근데 이 문제는 부모 노드를 지정해서 데이터를 입력해주기 때문에 풀이가 더 간단합니다.
BFS 탐색 시 깊이 정보만 저장해주면 나머지 과정은 모두 동일합니다.
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 1929 소수 구하기 - 에라토스테네스의체 (0) | 2024.02.12 |
---|---|
[백준 C++] 11438 LCA 2 - 최소공통조상 (1) | 2024.02.12 |
[백준 C++] 11437 LCA - 최소공통조상 (1) | 2024.02.12 |
[백준 C++] 11505 구간 곱 구하기 - 세그먼트트리 (1) | 2024.02.12 |
[백준 C++] 10868 최솟값 - 세그먼트트리 (1) | 2024.02.12 |