P11252 [KTSC 2024 R2] 岛屿

· · 题解

被诈骗了。

首先原来有 n 个点和 2n - 3 条边，而构造出两棵不交的树需要 2n - 2 条边，所以不操作肯定不行。

操作一次后有 n + 1 个点和 2n 条边，边数恰好足够，所以我们思考只操作一次是否可行。

答案是可以。我们可以选一个边上的小三角形进行操作。然后构造可以每次删除度数为 2 的点，其恰好有一条边属于 T_1，恰好有一条边属于 T_2。直到只剩 4 个点时特殊构造。

可以证明点数 > 4 时一定存在度数为 2 的点。考虑初始的边构成了正 n 边形的一个三角剖分，所以边缘的小三角形对应一个度数为 2 的点。所以删度数为 2 的点等价于删除最外面的小三角形。

时间复杂度 O(n)。

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

int add_vertex(int, int, int);
void report(vector< array<int, 2> >);

const int maxn = 200100;

int n, deg[maxn];
bool vis[maxn];
vector<int> G[maxn];

void construct_two_trees(int _n, vector<int> _u, vector<int> _v) {
    n = _n;
    for (int i = 0; i < n; ++i) {
        G[i].pb((i + 1) % n);
        G[(i + 1) % n].pb(i);
    }
    for (int i = 0; i < n - 3; ++i) {
        int u = _u[i], v = _v[i];
        G[u].pb(v);
        G[v].pb(u);
    }
    for (int i = 0; i < n; ++i) {
        deg[i] = (int)G[i].size();
    }
    vector< array<int, 2> > A, B;
    for (int u = 0; u < n; ++u) {
        if (deg[u] == 2) {
            int v = (u + n - 1) % n, w = (u + 1) % n;
            add_vertex(u, v, w);
            G[u].pb(n);
            G[n].pb(u);
            G[v].pb(n);
            G[n].pb(v);
            G[w].pb(n);
            G[n].pb(w);
            A.pb(array<int, 2>{u, v});
            A.pb(array<int, 2>{v, w});
            A.pb(array<int, 2>{w, n});
            B.pb(array<int, 2>{u, w});
            B.pb(array<int, 2>{u, n});
            B.pb(array<int, 2>{v, n});
            break;
        }
    }
    queue<int> q;
    for (int i = 0; i < n; ++i) {
        deg[i] = (int)G[i].size();
        if (deg[i] == 2) {
            q.push(i);
        }
    }
    while (q.size()) {
        int u = q.front();
        q.pop();
        if (vis[u]) {
            continue;
        }
        vis[u] = 1;
        int v = 0, w = 0;
        for (int x : G[u]) {
            if (!vis[x]) {
                (v ? w : v) = x;
                if ((--deg[x]) == 2) {
                    q.push(x);
                }
            }
        }
        A.pb(array<int, 2>{u, v});
        B.pb(array<int, 2>{u, w});
    }
    report(A);
    report(B);
}