[C++] 백준 3584 - Nearest Common Ancestors (dfs, 최소 공통 조상, 트리)

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. 참고

 

 

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!