CS Academy Round #38: F. Tree Antichain (Hard)
間に合わず。方針は合ってた。
problem
木が与えられる。その頂点の順列で、その列で隣り合うものは木上で隣り合わないようなものを答えよ。 ただし辞書順最小とする。
solution
貪欲。基本的に「それを使っても星型ができない」を満たすなら使ってよい。 次数が最大のものをpriority queueで管理しつつ番号が小さいものから取っていけばよい。 $O(N \log N)$。
最後の数個は丁寧にやる必要がある。
例えば頂点数$1$なら自明な星型であるが、それがだめなら必ず不可能である。
簡単には、残り少なくなったらnext_permutation
をするようにするとよい。
implementation
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <queue>
#include <set>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;
vector<int> solve(int n, vector<set<int> > g) {
repeat (i, n) {
if (g[i].size() == n - 1) {
return vector<int>(); // star
}
}
set<int> unused;
repeat (i, n) {
unused.insert(unused.end(), i);
}
vector<int> chain;
constexpr int size_limit = 7;
if (unused.size() >= size_limit) {
vector<int> used_edge(n);
priority_queue<pair<int, int> > que;
repeat (i, n) {
que.emplace(g[i].size(), i);
}
auto pred = [&](int i) {
assert (unused.size() >= size_limit);
// it must be not connected
if (not chain.empty() and g[chain.back()].count(i)) {
return false;
}
// it must not make a star node
while (true) {
int degree, j; tie(degree, j) = que.top();
if (degree != g[j].size() - used_edge[j]) {
que.pop();
que.emplace(g[j].size() - used_edge[j], j);
continue;
}
if (not unused.count(j)) {
que.pop();
continue;
}
if (i != j and degree == unused.size() - 2 and not g[i].count(j)) {
return false;
}
break;
}
return true;
};
while (unused.size() >= size_limit) {
int i = -1;
for (int j : unused) {
if (pred(j)) {
i = j;
break;
}
}
assert (i != -1);
unused.erase(i);
for (int j : g[i]) {
used_edge[j] += 1;
}
chain.push_back(i);
}
}
vector<int> xs(unused.begin(), unused.end());
whole(sort, xs);
do {
bool valid = true;
if (not chain.empty() and g[chain.back()].count(xs[0])) {
valid = false;
}
repeat (i, xs.size() - 1) {
if (g[xs[i]].count(xs[i + 1])) {
valid = false;
}
}
if (valid) {
chain.insert(chain.end(), xs.begin(), xs.end());
return chain;
}
} while (whole(next_permutation, xs));
assert (false);
}
int main() {
int testcases; scanf("%d", &testcases);
while (testcases --) {
int n; scanf("%d", &n);
vector<set<int> > g(n);
repeat (i, n - 1) {
int x, y; scanf("%d%d", &x, &y); -- x; -- y;
g[x].insert(y);
g[y].insert(x);
}
vector<int> result = solve(n, g);
if (result.empty()) {
printf("-1\n");
} else {
repeat (i, n) {
printf("%d%c", result[i] + 1, i + 1 == n ? '\n' : ' ');
}
}
}
return 0;
}