由于两者是独立的，我们希望两者的$p$和$q$都最大

考虑最大的$p$，先全部邀请，此时要增大$p$显然必须要删去当前度数最小的点，不断删除之后将每一次度数最小值对答案取max即可

对于$q$也即最大独立集，并没有很好的解法，但考虑不断加入一个节点$x$，并删去$x$以及与$x$相邻的节点，重复此过程直至原图为空即得到了一个独立集

每一次贪心选择度数最小的节点$x$，显然$x$的度数一定不超过$p$，换言之每一次至多删去$p+1$个节点，最终要删去所有节点，即有$\lceil\frac{n}{p+1}\rceil\le q$

接下来要证明$\lfloor\frac{n}{q+1}\rfloor\le p$，注意到$\lfloor\frac{n}{q+1}\rfloor\le \lceil\frac{n}{q}\rceil-1$，而根据$\lceil\frac{n}{p+1}\rceil\le q$有$\lceil\frac{n}{q}\rceil\le p+1$，即得证

（用了快读+快输还是TLE了一个点）

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define N 100005
  4 set<pair<int,int> >s;
  5 vector<int>ans;
  6 struct Edge{
  7     int nex,to;
  8 }edge[N<<1];
  9 int E,t,n,m,x,y,a[11],head[N],r[N],rr[N],vis[N];
 10 int read(){
 11     int x=0;
 12     char c=getchar();
 13     while ((c<'0')||(c>'9'))c=getchar();
 14     while ((c>='0')&&(c<='9')){
 15         x=x*10+c-'0';
 16         c=getchar();
 17     }
 18     return x;
 19 }
 20 void write(int x){
 21     a[0]=0;
 22     while (x){
 23         a[++a[0]]=x%10;
 24         x/=10;
 25     }
 26     for(int i=a[0];i;i--)putchar(a[i]+'0');
 27 }
 28 void add(int x,int y){
 29     edge[E].nex=head[x];
 30     edge[E].to=y;
 31     head[x]=E++;
 32 }
 33 int main(){
 34     t=read();
 35     while (t--){
 36         n=read(),m=read();
 37         E=0;
 38         memset(head,-1,sizeof(head));
 39         memset(r,0,sizeof(r));
 40         for(int i=1;i<=m;i++){
 41             x=read(),y=read();
 42             add(x,y);
 43             add(y,x);
 44             r[x]++,r[y]++;
 45         }
 46         memcpy(rr,r,sizeof(r));
 47         s.clear();
 48         memset(vis,0,sizeof(vis));
 49         for(int i=1;i<=n;i++)s.insert(make_pair(r[i],i));
 50         for(int i=1;i<=n;i++){
 51             x=(*s.begin()).second;
 52             s.erase(s.begin());
 53             vis[x]=i;
 54             for(int i=head[x];i!=-1;i=edge[i].nex)
 55                 if (!vis[edge[i].to]){
 56                     s.erase(make_pair(r[edge[i].to],edge[i].to));
 57                     s.insert(make_pair(--r[edge[i].to],edge[i].to));
 58                 }
 59         }
 60         for(int i=1;i<=n;i++)r[0]=max(r[0],r[i]);
 61         for(int i=1;i<=n;i++)
 62             if (r[0]==r[i])x=i;
 63         ans.clear();
 64         for(int i=1;i<=n;i++)
 65             if (vis[i]>=vis[x])ans.push_back(i);
 66         write(ans.size());
 67         putchar(' ');
 68         for(int i=0;i<ans.size();i++){
 69             write(ans[i]);
 70             putchar(' ');
 71         }
 72         putchar('\n');
 73         memcpy(r,rr,sizeof(r));
 74         s.clear();
 75         ans.clear();
 76         memset(vis,0,sizeof(vis));
 77         for(int i=1;i<=n;i++)s.insert(make_pair(r[i],i));
 78         while (!s.empty()){
 79             x=(*s.begin()).second;
 80             s.erase(s.begin());
 81             vis[x]=1;
 82             ans.push_back(x);
 83             for(int i=head[x];i!=-1;i=edge[i].nex)
 84                 if (!vis[edge[i].to]){
 85                     vis[edge[i].to]=1;
 86                     s.erase(make_pair(r[edge[i].to],edge[i].to));
 87                     for(int j=head[edge[i].to];j!=-1;j=edge[j].nex)
 88                         if (!vis[edge[j].to]){
 89                             s.erase(make_pair(r[edge[j].to],edge[j].to));
 90                             s.insert(make_pair(--r[edge[j].to],edge[j].to));
 91                         }
 92                 }
 93         }
 94         write(ans.size());
 95         putchar(' ');
 96         for(int i=0;i<ans.size();i++){
 97             write(ans[i]);
 98             putchar(' ');
 99         }
100         putchar('\n');
101     }
102 }

View Code