글 읽기 - 반례를 찾아주세요!

sungdd2 4년 전 0

재귀로 구현했구요

보시면 아시겠지만 deque를 이용했습니다.

여기 예시에 나온 반례들도 전부 맞다고 나오는데 어디가 틀린 걸까요??

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

//vector<int> list[100000];
deque<int> list[100000];
int parent[100000] = { -1, };
int input;

int recur(int now);


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

	cin >> input;

	

	parent[0] = 0;

	for (int i = 0; i < input-1; i++) {
		int a, b;
		cin >> a >> b;
		if (a == 1) {
			list[0].push_back(b);
		}
		else if (b == 1) {
			list[0].push_back(a);
		}
		else {
			list[a - 1].push_back(b);
			list[b - 1].push_back(a);
		}
	}

	int now = 1;

	
	recur(1);

	for (int i = 1; i < input; i++) {
		cout << parent[i] << '\n';
	}


	return 0;
}

int recur(int now) {

	if (now != 1) {
		while (!list[now - 1].empty()) {
			int tmp = list[now - 1].front();
			list[now - 1].pop_front();
			list[tmp - 1].pop_front();
			parent[tmp - 1] = now;
			recur(tmp);
		}
	}
	else {
		while (!list[0].empty()) {
			int tmp = list[0].front();
			parent[tmp - 1] = 1;
			list[0].pop_front();
			recur(tmp);
		}
	}

	return 0;
}

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

문제

문제

출처

ICPC

반례를 찾아주세요!

sungdd2 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말