Lca

LCA

문제 사이트

코드

struct Node {
	vector<int> childs;
	int depth = 0;
};

#define MAX_SIZE 100001
Node nodes[MAX_SIZE];
int  parentTB[MAX_SIZE][20];

void DFS(int cur, int parent = 0)  // parent default value 를 -1 로 두지 말자
{
	nodes[cur].depth = nodes[parent].depth + 1;
	parentTB[cur][0] = parent;
	for (auto child : nodes[cur].childs)
		if(parent != child)
			DFS(child, cur);
}

int LCA(int a, int b)
{
	int i;
	if (nodes[a].depth < nodes[b].depth) swap(a, b);
    for(int dff = nodes[a].depth - nodes[b].depth; dff > 0; )
    {
		for (i = 0; 2 << i <= dff; i++);
		a = parentTB[a][i];
        dff = nodes[a].depth - nodes[b].depth;
    }

	while (a != b)
	{
		for (i = 1; parentTB[a][i] != parentTB[b][i]; i++);
		a = parentTB[a][i-1];
		b = parentTB[b][i-1];
	}
	
	return a;
}

int main()
{
	int n, m, tmp1, tmp2;
	cin >> n;;
	for (int i = 0; i < n - 1; i++)
	{
		cin >> tmp1 >> tmp2;
		nodes[tmp1].childs.push_back(tmp2);
		nodes[tmp2].childs.push_back(tmp1);
	}

​	DFS(1, 0);
​	for (int i = 1; i < 20; i++)
​		for (int j = 1; j <= n; j++)
​			parentTB[j][i] = parentTB[parentTB[j][i-1]][i-1];
​			

	cin >> m;
	while (m--)
	{
		cin >> tmp1 >> tmp2;
		cout << LCA(tmp1, tmp2) << '\n';
	}
}

시간 복잡도

O(\((\mathrm{N} + \mathrm{M})\log{\mathrm{N}}\))

설명

Node 마다 1, 2, 4, 8 … 으로 지수적으로 올라간 부모의 정보를 이용해 LCA 알고리즘을 Log 단위로 낮추는 것이 목표.

총 2가지 단계가 있다.

단계 1. 트리 구성

• DFS 로 트리를 구성 하면서 노드마다 루트로부터의 Depth 를 저장한다.
• 그리고 현재 Node 의 지수적으로 올라간 부모의 정보를 ParentTB 에 기록한다.

단계 2. LCA

• ParentTB 를 이용해서 Depth 가 큰 쪽이 다른쪽 Depth 와 같게 되도록 부모로 올린다.
• ParentTB 를 이용해서 처음으로 달라지는 지점 이전 부모로 이동한다. 부모가 같아질 때까지 이를 반복한다. 최악 Log(N) 번 while 문을 돌게 된다.