<백준> 11437

LCA

문제
N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.
두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

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

출력
M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

BFS와 DFS 두개로 문제를 풀어봤다.

int n, m;
vector<vector<int>> tree;
vector<int> parent;
vector<int> depth;
vector<bool> visited;

void BFS(int node)
{
	queue<int> q;
	q.push(node);
	visited[node] = true;
	int level = 1;
	int now_size = 1;
	int count = 0;

	while (!q.empty())
	{
		int nowNode = q.front();
		q.pop();

		for (int next : tree[nowNode])
		{
			if (!visited[next])
			{
				visited[next] = true;
				q.push(next);
				parent[next] = nowNode;
				depth[next] = level;
			}
		}
		count++;
		if (count == now_size)
		{
			count = 0;
			now_size = q.size();
			level++;
		}
	}
}

int executeLCA(int a, int b)
{
	if (depth[a] < depth[b])
	{
		int temp = a;
		a = b;
		b = temp;
	}
	while (depth[a] != depth[b])
	{
		a = parent[a];
	}
	while (a != b)
	{
		a = parent[a];
		b = parent[b];
	}
	return a;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;

	tree.resize(n + 1);
	parent.resize(n + 1);
	depth.resize(n + 1);
	visited.resize(n + 1);

	for (int i = 0; i < n - 1; i++)
	{
		int s, e;
		cin >> s >> e;
		tree[s].push_back(e);
		tree[e].push_back(s);
	}

	BFS(1);
	cin >> m;

	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		int LCA = executeLCA(a,b);
		cout << LCA << "\n";
	}
}

DFS로 푼 문제다.

int n, m;
vector<vector<int>> tree;
vector<int> parent;
vector<int> depth;
vector<bool> visited;

void DFS(int node, int level)
{
	visited[node] = true;
	depth[node] = level;

	for (int next : tree[node])
	{
		if (!visited[next])
		{
			visited[next] = true;
			parent[next] = node;
			DFS(next, level + 1);
		}
	}
}

int executeLCA(int a, int b)
{
	if (depth[a] < depth[b])
	{
		int temp = a;
		a = b;
		b = temp;
	}
	while (depth[a] != depth[b])
	{
		a = parent[a];
	}
	while (a != b)
	{
		a = parent[a];
		b = parent[b];
	}
	return a;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;

	tree.resize(n + 1);
	parent.resize(n + 1);
	depth.resize(n + 1);
	visited.resize(n + 1);

	for (int i = 0; i < n - 1; i++)
	{
		int s, e;
		cin >> s >> e;
		tree[s].push_back(e);
		tree[e].push_back(s);
	}

	DFS(1,0);
	cin >> m;

	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		int LCA = executeLCA(a,b);
		cout << LCA << "\n";
	}
}