Luogu

LOJ

分析

题目中的条件相当于 $(p+1)(q+1)\geq n$。

第一问可以每次选一个度数最小的点删去，然后更新答案。用堆维护可以做到 $\mathcal{O}(n\log n)$。

第二问是求独立集，也可以每次选一个度数最小的点，然后把它和与它相连的点都删去。

可以证明这样子一定是满足条件的。设第 $i$ 次删掉的点的度数为 $d_i$，那么有 $\sum_{i=1}^q(d_i+1)\geq n$，而 $p=\max\{d_i\}$，故 $(p+1)(q+1)\geq n$ 必成立。

当然你也可以直接随机化来戏弄出题人

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10000+10;

int n,m,deg[N],odeg[N],vis[N];
vector<int> E[N],vp,vq;
priority_queue<pii,vector<pii>,greater<pii>> Q;

int main() {
    int T=read();
    while (T--) {
        n=read(),m=read();
        for (int i=1;i<=m;++i) {
            int u=read(),v=read();
            E[u].emplace_back(v),++odeg[v];
            E[v].emplace_back(u),++odeg[u];
        }
        memset(vis,0,sizeof(vis)),memcpy(deg,odeg,sizeof(deg));
        int mxp=n,pos=0;
        for (int i=1;i<=n;++i) Q.emplace(deg[i],i),mxp=min(mxp,deg[i]);
        while (!Q.empty()) {
            int u=Q.top().second; Q.pop();
            if (vis[u]) continue;
            vis[u]=1,vp.emplace_back(u);
            for (int v:E[u]) --deg[v],Q.emplace(deg[v],v);
            if (Q.top().first>mxp) mxp=Q.top().first,pos=vp.size();
        }
        memset(vis,0,sizeof(vis)),memcpy(deg,odeg,sizeof(deg));
        for (int i=1;i<=n;++i) Q.emplace(deg[i],i);
        while (!Q.empty()) {
            int u=Q.top().second; Q.pop();
            if (vis[u]) continue;
            vis[u]=1,vq.emplace_back(u);
            for (int v:E[u]) vis[v]=1;
        }
        printf("%d",n-pos);
        for (int i=pos;i<n;++i) printf(" %d",vp[i]);
        puts("");
        printf("%lu",vq.size());
        for (int i:vq) printf(" %d",i);
        puts("");

        vp.clear(),vq.clear();
        for (int i=1;i<=n;++i) odeg[i]=0,E[i].clear();
    }
    return 0;
}