글 읽기 - 반례가 궁금합니다.

kkw564 6년 전 0

트리의 부모를 찾는 과정에서 특정한 알고리즘을 적용 시키지 않고 해결 할 수 있다 느꼈는데 이에 대한 반례가 어떤 것이 있나요?

#include <iostream>
#include <cstdio>
#include <algorithm>

#define SWAP(a,b) {int tmp; tmp = a; a = b; b = tmp;}
using namespace std;

// tree[].first = 연결된 것을 표현 
// tree[].second = 부모 노드를 표현
typedef pair<int, int> pii;
pii tree[100002];
int ans[100002];

bool comp(const pii &a, const pii &b)
{
	return a.first < b.first;
}
int main()
{
	int n;
	int from, to;

	scanf("%d", &n);

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

		if(from > to)
			SWAP(from, to);

		tree[i].first = from;
		tree[i].second = to;
	}

	sort(tree, tree + n - 1, comp);

	for (int i = 0; i < n - 1; i++)
	{
		// 부모 노드를 모르는 상태라면(ans는 부모 노드를 알게해준다.)
		if (ans[tree[i].second] == 0)
			ans[tree[i].second] = tree[i].first;

		else
			ans[tree[i].first] = tree[i].second;
	}

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

	return 0;
}

uk7880 6년 전 1

5
1 4
4 5
5 3
3 2

dsemnai 5달 전 1

3 5 1 4 맞죠

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

문제

문제

출처

ICPC

반례가 궁금합니다.

kkw564 6년 전 0

uk7880 6년 전 1

dsemnai 5달 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말