글 읽기 - 반례 부탁드립니다!

fantasy7772 2년 전 0

노드의 차수를 기준으로 1차적으로 얼리어답터가 될 노드들을 정하고 정보가 전달되어지지 않는 노드들을 다시 확인하고 얼리어답터를 결정하는 방식으로 코드를 짜보았는데 반례를 잘 모르겠습니다.

#include<iostream>
#include<vector>
using namespace std;
int N;
int degree[1'000'001];
vector<int> vec[1'000'001];
bool covered[1'000'001];
bool early[1'000'001];
int answer = 0;
void solve() {
	cin >> N;
	for (int i = 1; i <= N - 1; i++) {
		int u, v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
		degree[u]++;
		degree[v]++;
	}
	for (int i = 1; i <= N; i++) {
		if (degree[i] == 1) {
			int close = vec[i][0];
			covered[i] = true;
			if (early[close]) continue;
			else {
				answer++;
				early[close] = true;
				covered[close] = true;
				for (int j = 0; j < vec[close].size(); j++) {
					int close2 = vec[close][j];
					covered[close2] = true;
				}
			}

		}
	}
	for (int i = 1; i <= N; i++) {
		if (!covered[i]) {
			answer++;
			for (int j = 0; j < vec[i].size(); j++) {
				if (!covered[vec[i][j]]) covered[vec[i][j]] = true;
			}
		}
	}
}

int main() {
	solve();
	cout << answer;
	return 0;
}

jjang36524 2년 전 1

이 방법으로는 문제를 풀 수 없습니다. tree dp를 알아보세요

fantasy7772 2년 전 0

넵 감사합니다

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

문제

문제

출처

ICPC

반례 부탁드립니다!

fantasy7772 2년 전 0

jjang36524 2년 전 1

fantasy7772 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말