题目描述
Cirno被推荐了一个游戏，她决定今天和大妖精一起玩。最初，有一个包含2 × n个顶点和m条边的图。在每一轮中，Cirno和大妖精都必须选择一个不同的顶点。所选顶点的度数必须相同。然后，Cirno和大妖精将从图中移除它们。
现在Cirno想知道是否有办法从给定的图中移除所有顶点。如果存在，请给出一个例子。
题解
该题有2 * n个顶点，一定能删完。
为什么一定能删完？可以通过反证法：设不能删完，剩余2 * x个点，且每个点的度数各不相同。
由于最大度数不可能超过2 * x - 1，那么2 * x个点的度数就是0，1，2，...，2 * x - 1。
观察到有一个点的度数为2 * x - 1 ，则剩余所有点都与这个点有边；但有一个点度数为0，则剩余所有点都与这个点无边。
二者自相矛盾。此种情况不存在。所以一定有解，且解与删除顺序无关。
考虑一个时间复杂度较优的解法：可以通过set维护度数，每次删除度数最大的两个点。时间复杂度稳定在O(nlogn)。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+7;
int n,m,en=0,h[N],du[N];
struct Edge{
int v,nxt;
}e[N<<1];
set<int>s[N<<1];
void adde(int u,int v){
e[++en].v=v,e[en].nxt=h[u],h[u]=en;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
adde(u,v),adde(v,u);
du[u]++,du[v]++;
}
for(int i=1;i<=n*2;i++)s[du[i]].insert(i);
int t=m;
while(t>=0){
if(s[t].size()>=2){
int x=*s[t].begin();
s[t].erase(x);
int y=*s[t].begin();
s[t].erase(y);
cout<<x<<" "<<y<<"\n";
du[x]=du[y]=0;
for(int i=h[x];i;i=e[i].nxt){
int v=e[i].v;
if(du[v]>0){
s[du[v]].erase(v);
du[v]--;
s[du[v]].insert(v);
}
}
for(int i=h[y];i;i=e[i].nxt){
int v=e[i].v;
if(du[v]>0){
s[du[v]].erase(v);
du[v]--;
s[du[v]].insert(v);
}
}
}
else t--;
}
return 0;
}