CS Academy Round #38: F. Tree Antichain (Hard)

,

https://csacademy.com/contest/round-38/task/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;
}