11437

LCA를 푸는 문제다. LCA 최적화 알고리즘은 이미 정리해두었으니 넘기자.

문제에 주어진 간선을 가지고 어떻게 트리의 형태로 만드느냐가 LCA를 풀기 위한 조건이다.

일반적으로 간선에 대한 자료구조들은 2차원 배열을 이용해서 표현하지만 N이 10000을 넘어가면 2차원 배열의 최대 크기를 초과하게된다.

C++에서는 vector를 사용해서 위와같은 문제를 간단히 해결 할 수 있지만 경우에 따라서 vector를 사용하지 못하는 상황도 존재한다.

간선 정보들을 필요할 때 마다 신속히 접근하는 자료구조가 중요한데 매번 모든 간선 정보O(N)를 찾아볼 수도 없을 노릇이다.

이런 경우에는 특정 경우 대해서 정렬을 해주는 방법이 유용하다.

간선에 대한 정보를 from들에 대해서 정렬을 해주고 각각의 시작점을 확인해서 찾아 볼 수 있다.

 

bool compare(Edge a, Edge b) {
	if (a.from < b.from)
		return true;
	return false;
}

int main() {

	for (i = 0; i < N - 1; i++) {
		scanf("%d %d", &from, &to);
		edge[nredges].par = from, edge[nredges].child = to;
		nredges++;
		edge[nredges].par = to, edge[nredges].child = from;
		nredges++;
	}

	sort(&edge[1], &edge[nredges], compare);

	for (i = 0; i < nredges; i++) {
		if (!stIdx[edge[i].par])
			stIdx[edge[i].par] = i;
	}

	queue[nrque++] = 1;

	for (i = 0; i < nrque; i++) {
		front = queue[i];
		if (visited[front])
			continue;
		visited[front] = 1;
		for (j = stIdx[front]; edge[j].par == front; j++) {
			if (visited[edge[j].child])
				continue;
			child = edge[j].child;
			queue[nrque++] = child;
			depth[child] = depth[front] + 1;

			parent[child][0] = front;
			for (k = 1; k < 20; k++) 
				parent[child][k] = parent[parent[child][k - 1]][k - 1];
		}
	}

	scanf("%d", &M);

	return 0;

}

(*여기서는 방문 순서는 중요하지 않기 때문에 to에 대해서는 정렬을 해주지 않았지만 특정한 to에 대해서 접근이 필요하다면 to에 대해서도 추가적인 정렬을 수행해 from에 대한 접근(O(1)) + to에 대한 이진탐색(O(log(M)) M은 동일한 from 간선 개수 로 빠르게 접근 할 수 있다.)

이렇게 간선 정보들을 정렬해서 정리해두었으면 이제 트리의 형태를 만들어야하는데

이거는 BFS로 구현하던지 아니면 DFS로 구현하던지 하면 된다.

나는 BFS가 사용하기 편해 BFS로 구현했다.

각각의 노드들을 한 번만 방문하면 된다는 점을 유의하자

 
	for (i = 0; i < nrque; i++) {
		front = queue[i];
		if (visited[front])
			continue;
		visited[front] = 1;
		for (j = stIdx[front]; edge[j].par == front; j++) {
			if (visited[edge[j].child])
				continue;
			child = edge[j].child;
			queue[nrque++] = child;
			depth[child] = depth[front] + 1;

			parent[child][0] = front;
			for (k = 1; k < 20; k++) 
				parent[child][k] = parent[parent[child][k - 1]][k - 1];
		}
	}