글 읽기 - 어떤부분에서 틀렸습니다가 뜬걸까요

whwoals21 4년 전 0

예제도 출력이 잘되고

혹시모를 예제로

순서대로 안나오고

1 5

같은걸 넣어도 잘 출력이 되는데

어떤 부분에서 틀렸습니다 일까요?

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

struct Node
{
	int data;
	Node* parent = NULL;
	Node()
	{
		data = NULL;
		parent = NULL;
	}
};

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

	int n;
	cin >> n;
	Node new_node[100001];
	int last = 0;
	vector<pair<int, int>> vec(100001);
	for (int i = 0; i < n - 1; i++)
	{
		int a, b;
		cin >> a >> b;
		new_node[a].data = a;
		new_node[b].data = b;
		if (a == 1 || b == 1)
		{
			if (a == 1)
			{
				new_node[b].parent = &new_node[a];
				vec[b] = { b, new_node[b].parent->data };
			}
			else
			{
				new_node[a].parent = &new_node[b];
				vec[a] = { a, new_node[a].parent->data };
			}
		}

		if (new_node[a].parent == NULL && a != 1)
		{
			new_node[a].parent = &new_node[b];
			vec[a] = { a, new_node[a].parent->data };
		}
		else if (new_node[b].parent == NULL && b != 1)
		{
			new_node[b].parent = &new_node[a];
			vec[b] = { b, new_node[b].parent->data };
		}
		if (a < b)
			last = b;
		else
			last = a;

	}
	
	sort(vec.begin(), vec.end());
	
	for (int i = 2; i <= 100000; i++)
	{
		if(vec[i].first != 0)
			cout << vec[i].second << '\n';
	}

	return 0;
}

yehyun 4년 전 2

입력으로 들어온 임의의 두 노드 a, b가 모두 새로운 노드일 때 (이전에 입력으로 들어 온 적 없을 때)

48-52줄의 코드에 의해 a의 부모 노드가 b가 되는데, 이것은 옳지 않습니다.

예컨대 아래와 같은 입력이 들어오면

둘째 줄에서 3의 부모가 2가 되고,

셋째 줄에서 3의 부모가 다시 1이 되며,

끝까지 2의 부모는 초기화되지 않습니다.

입력을 받으면서 실시간으로 부모 노드를 결정하시기보다는

인접행렬이나 인접리스트를 채운 뒤에 1을 루트로 하는 BFS나 DFS를 해서 각 노드의 부모 노드를 찾는 것이 좋을 것 같습니다.

3
3 2
1 3

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

문제

문제

출처

ICPC

어떤부분에서 틀렸습니다가 뜬걸까요

whwoals21 4년 전 0

yehyun 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말