题解 CF1738F 【Connectivity Addicts】

Sol1 · 2023-01-27 22:46:20 · 题解

首先观察到如果知道整个图，那么一个连通块染两个颜色非常愚蠢。

但这没用啊，因为 n 次询问咋说也找不出整个图。所以可以考虑到这题实际上是希望我们在 n 次询问内找出一些边使得这个图“足够连通”。

然后有个简单的想法，就是每次选一个点出来遍历一圈，把遍历到的点记录一下，然后只遍历之前没遍历过的点。从贪心的角度讲，选点自然是选度数最大的那个让它尽量连通。这样找出若干条边之后，把找出的边生成的连通块（在原图里面一定也是连通块）染成一个颜色。

注意到这样找出边一定可以满足那个 s<n^2 的条件，因为每一个点一定处于一个大小比本身度数更大的连通块里面。

然后交上去发现 WA 了，冷静一下会发现这样做会超出 n 次操作。

为了优化，考虑一下上面那个“每一个点一定处于一个大小比本身度数更大的连通块里面”。

注意到由于我们按度数从大到小选，所以如果在遍历的过程中遍历到了一个之前遍历过的点，那么连上这条边之后当前点就满足上述条件了，就可以直接 break。

这样由于每条新边都会改变连通性，于是操作总数 \leq n-1。

#include <bits/stdc++.h>
using namespace std;

int d[1005], idx[1005], f[1005], rnk[1005];
bool vis[1005];

inline int GetRoot(int v) {
    if (f[v] == v) return v;
    return f[v] = GetRoot(f[v]);
}

inline void Merge(int x, int y) {
    int u = GetRoot(x), v = GetRoot(y);
    f[u] = v;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1;i <= n;i++) cin >> d[idx[i] = i];
        for (int i = 1;i <= n;i++) vis[i] = 0;
        for (int i = 1;i <= n;i++) f[i] = i;
        sort(idx + 1, idx + n + 1, [&](const int &x, const int &y) {
            return d[x] > d[y];
        });
        for (int i = 1;i <= n;i++) rnk[idx[i]] = i;
        for (int i = 1;i <= n;i++) {
            if (!vis[idx[i]]) {
                for (int j = 1;j <= d[idx[i]];j++) {
                    cout << "? " << idx[i] << endl;
                    int v; cin >> v; vis[v] = 1;
                    if (rnk[GetRoot(v)] < i) {
                        Merge(v, idx[i]);
                        break;
                    }
                    Merge(v, idx[i]);
                }
            }
        }
        cout << "! ";
        for (int i = 1;i <= n;i++) cout << GetRoot(i) << " ";
        cout << endl;
    }
    return 0;
}