앳코더90 - 026 - Independent Set on a Tree（★4）

https://atcoder.jp/contests/typical90/tasks/typical90_z

026 - Independent Set on a Tree（★4）

 

7레벨은 이제 건너뛰도록 하자

 

하나의 트리 그래프가 주어질때 인접하지 않은 정점의 집합을 N/2개 출력하시오.

예제이다. 정점 하나를 잡고 시작해서 깊이를 기준으로 깊이가 짝수일때만 vector에 넣어서 정렬 후 출력했더니 테스트케이스 일부가 틀렸었다. 다시 생각해보니 내가 시작 정점을 1로 한거였는데 1이 끝이 아니고 어느 트리 노드의 일부일 수 도 있어서 정점의 개수가 부족할 수 도 있어서 라고 생각을 했고 짝수일때, 홀수일때 모두 저장해주고 출력해줬더니 맞았다는 결과를 받았다. 스폐셜 저지인지 아닌지는 알 수 없어서 후자의 경우를 생각하지 못했던 것 같다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <numeric>
#include <random>
#include <iostream>
#include <unordered_map>
//#include <atcoder/all>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

using namespace std;
//using namespace atcoder;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;

const int INF = 2000000000;
const double pi = 3.14159265358979;
const int MOD = 100000;

void yesno(bool a)
{
	if (a)
		cout << "YES\n";
	else
		cout << "NO\n";
}

int N;
vector<int> graph[100002];
int visited[1000002];
vector<int> ans;
vector<int> ans2;

void dfs(int start, int depth)
{
	visited[start] = 1;
	if (depth % 2 == 1)
		ans.push_back(start);
	else
		ans2.push_back(start);

	for (auto i : graph[start])
	{
		if (visited[i])
			continue;

		dfs(i, depth + 1);
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N;

	rep(i, N-1)
	{
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	
	dfs(1, 1);

	sort(ans.begin(), ans.end());
	sort(ans2.begin(), ans2.end());

	if (ans.size() > ans2.size())
	{
		rep(i, N/2)
		{
			cout << ans[i] << " ";
		}
	}
	else
	{
		rep(i, N / 2)
		{
			cout << ans2[i] << " ";
		}
	}

	return 0;
}