글 읽기 - 틀린 케이스를 못찾겠습니다.

tddhot2 7년 전 0

- 문제 풀이 방법은 공통조상을 찾을 두 노드 중에서 깊이가 더 높은 것을 깊이를 줄여가며 두 노드의 깊이를 맞춥니다. 맞춘이후로는 깊이를 하나씩 내려가며(부모 노드로 이동해가며) 서로 같을 노드 값을 찾을 때까지 진행합니다.

- 처음에 잠깐 "채점 중"이었다가 바로0 "틀렸습니다"가 떴습니다. 예외 경우에 따로 존재할까요?

#include <iostream>
#include <vector>
using namespace std;

//first = parent node num, second = depth
pair<int, int> graph[50001];


int FindCommonParent(int nodeA, int nodeB)
{
	int a, b;
	if(graph[nodeA].second>graph[nodeB].second)
	{
		a = nodeA;
		b = nodeB;
	}
	else if (graph[nodeA].second <= graph[nodeB].second)
	{
		a = nodeB;
		b = nodeA;
	}

	while (graph[a].second != graph[b].second)
	{
		a = graph[a].first;
	}
		
	// to check for whether two nodes has same depth of tree
	//cout << "Depth of a : " << graph[a].second << " , Depth of b : " << graph[b].second << endl;

	while (1)
	{
		if (a == b)
			return a;
		a = graph[a].first;
		b = graph[b].first;
	}
}


int main()
{
	pair<int, int> temp(0, 0);
	for (int i = 0; i <= 50000; i++)
		graph[i] = temp;
	int n;
	cin >> n;

	for (int i = 0; i < n - 1; i++)
	{
		int nodeA, nodeB;
		scanf("%d %d", &nodeA, &nodeB);

		if (nodeA == 1)
		{
			graph[nodeB].first = 1;
			graph[nodeB].second = 1;
		}
		else if (nodeB == 1)
		{
			graph[nodeA].first = 1;
			graph[nodeA].second = 1;
		}
		else if (nodeA != 1 && nodeB != 1)
		{
			if (graph[nodeA].first != 0)
			{
				graph[nodeB].first = nodeA;
				graph[nodeB].second = graph[nodeA].second + 1;
			}
			else if (graph[nodeB].first != 0)
			{
				graph[nodeA].first = nodeB;
				graph[nodeA].second = graph[nodeB].second + 1;
			}
		}
	}

	int m;
	int ans[10000];
	cin >> m;

	for (int i = 0; i < m; i++)
	{
		int nodeA, nodeB;
		scanf("%d %d", &nodeA, &nodeB);
		ans[i]=FindCommonParent(nodeA, nodeB);
	}

	for (int i = 0; i < m; i++)
		printf("%d\n", ans[i]);

	return 0;
}

naong606 7년 전 4

2 3

1 2

2 3

답이 2가 나와야하는데 0을 출력하네요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀린 케이스를 못찾겠습니다.

tddhot2 7년 전 0

naong606 7년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말