题意：
你有n个好友，他们之间有m对关系$(u,v)$表示u和v互相认识，认识没有传递性。
现在你想组织一场热闹的聚会和一场尴尬的聚会，定义如下：
- 一场热闹度为p的聚会请来了任意多位好友，对于每一位到场的好友来说都有至少p位他认识的好友也参加了聚会，且至少对于一位到场的好友来说现场恰好有p位他认识的好友；
- 一场尴尬度为q的聚会请来了恰好q位好友，且他们两两互不认识。
这两场聚会之间没有任何联系。
你希望p和q满足$\lfloor \frac{n}{p+1}\rfloor \leq q$且$\lfloor \frac{n}{q+1}\rfloor \leq p$，求一种合法方案。
$T\leq 32,n\leq 10000,m\leq 10^{5}$。
题解：
首先发现对于任意p/q，q/p越大越优，所以原问题可以拆成求最大的p和最大的q。
考虑求最大的p，显然可以依次尝试删除图中度数最小的点，尽管删除点数越多答案不一定越优，但记录最大答案及其删除个数即可。
考虑求最大的q，贪心的想法是依次取图中度数最小的点，并删除它和所有与它相邻的点。
但显然这样求出的并不是最大独立集。因为求一般图最大独立集是个NP问题。
不过，我们本身要求的并不是最大的q，而是任意一个满足$\lfloor \frac{n}{p+1}\rfloor \leq q$且$\lfloor \frac{n}{q+1}\rfloor \leq p$的q，所以有一个奇妙的结论：这样贪心是100%正确的。
证明：考虑p算法的过程，我们每次删除的点的度数一定$\leq p$。
而q算法删的点的度数比p只少不多，也就是说对于q中每次操作至多会删掉p+1个点。
那么显然q算法至少会运行$\lceil \frac{n}{p+1}\rceil$次，这也对应着该算法求出的q的下界。
于是求出的p和q一定满足题目中的限制条件（$(p+1)(q+1)>n$时两个条件均满足），证毕。
复杂度$O(T(n+m)logn)$（大概吧），需要稍加优化。
（也许运行q算法时直接删点不更新边权也是对的，但我并不想证明）
套路：
- 在有某些限制条件时瞎蒙一个贪心很可能是对的；
- 构造题可以考虑将若干个限制条件合并成一个较宽松的限制条件，一般很少有人喜欢把下界卡死（大概吧）。
代码：
#include<bits/stdc++.h>
#define maxn 10005
#define maxm 500005
#define inf 0x7fffffff
#define ll long long
#define mp make_pair
#define rint register int
#define debug(x) cerr<<#x<<": "<<x<<endl
#define fgx cerr<<"--------------"<<endl
#define dgx cerr<<"=============="<<endl
using namespace std;
int to[maxm],nxt[maxm],hd[maxn],vis[maxn],cnt;
int A[maxn],B[maxn],deg[maxn],D[maxn];
priority_queue<pair<int,int> > Q;
map<pair<int,int>,int> M;
inline int read(){
int x=0,f=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
inline void addedge(int u,int v){
to[++cnt]=v,nxt[cnt]=hd[u],hd[u]=cnt;
to[++cnt]=u,nxt[cnt]=hd[v],hd[v]=cnt;
}
int main(){
int T=read();
while(T--){
memset(A,0,sizeof(A));
memset(B,0,sizeof(B));
memset(hd,0,sizeof(hd));
memset(deg,0,sizeof(deg));
memset(vis,0,sizeof(vis));
M.clear(),cnt=0;
while(!Q.empty()) Q.pop();
int n=read(),m=read();
for(int i=1;i<=m;i++){
int u=read(),v=read(); if(u>v) swap(u,v);
if(M[mp(u,v)]) continue;
else addedge(u,v),M[mp(u,v)]=1,deg[u]++,deg[v]++;
}
memcpy(D,deg,sizeof(deg));
for(int i=1;i<=n;i++) Q.push(mp(-deg[i],i));
int ans=0,endpos=0;
while(!Q.empty()){
int u=Q.top().second,d=-Q.top().first;
Q.pop(); if(vis[u]) continue;
vis[u]=1,A[++A[0]]=u;
if(ans<-Q.top().first)
ans=-Q.top().first,endpos=A[0];
for(int i=hd[u];i;i=nxt[i])
if(!vis[to[i]])
Q.push(mp(-(--deg[to[i]]),to[i]));
}
memcpy(deg,D,sizeof(D));
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++) Q.push(mp(-deg[i],i));
while(!Q.empty()){
int u=Q.top().second,d=-Q.top().first;
Q.pop(); if(vis[u]) continue;
vis[u]=1,B[++B[0]]=u;
for(int i=hd[u];i;i=nxt[i]){
int v=to[i];
if(vis[v]) continue;
vis[v]=1;
for(int j=hd[v];j;j=nxt[j]){
int w=to[j];
if(vis[w]) continue;
Q.push(mp(-(--deg[w]),w));
}
}
}
printf("%d",n-endpos);
for(int i=endpos+1;i<=n;i++) printf(" %d",A[i]);
printf("\n");
printf("%d",B[0]);
for(int i=1;i<=B[0];i++) printf(" %d",B[i]);
printf("\n");
}
return 0;
}
热闹的聚会与尴尬的聚会