比赛链接

2022年江西省大学生程序设计竞赛（正式赛）

C.Graphic Game

给一个 \(2\times n\) 个点，\(m\) 条边，没有重边和自环的无向图，每次可以选择两个度数相等的点删除，求删完所有点的方案

解题思路

鸽笼原理

度数的可能取值有 $0,1,\dots,min(m,)

• 时间复杂度：\(O(nlogn)\)

代码

// Problem: Graphic Game
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/43898/C
// Memory Limit: 524288 MB
// Time Limit: 10000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
// #define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}


const int N=2e6+5,M=1e6+5;
int n,m,d[N];
int h[N],e[N],ne[N],idx;
set<int>deg[M];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int main()
{
    memset(h,-1,sizeof h);
    read(n),read(m);
    for(int i=1;i<=m;i++)
    {
    	int a,b;
    	read(a),read(b);
    	add(a,b),add(b,a);
    	d[a]++,d[b]++;
    }
    for(int i=1;i<=2*n;i++)deg[d[i]].insert(i);
    int t=m;
    while(t>=0)
    {
    	if(deg[t].size()>=2)
    	{
    		int x=*deg[t].begin();
    		deg[t].erase(deg[t].begin());
    		int y=*deg[t].begin();
    		deg[t].erase(deg[t].begin());
    		printf("%d %d\n",x,y);
    		d[x]=d[y]=0;
    		for(int i=h[x];~i;i=ne[i])
    		{
                int j=e[i];
    			if(d[j]>0)
    			{
    				deg[d[j]].erase(j);
    				d[j]--;
    				deg[d[j]].insert(j);
    			}
    		}
    		for(int i=h[y];~i;i=ne[i])
    		{
    			int j=e[i];
    			if(d[j]>0)
    			{
    				deg[d[j]].erase(j);
    				d[j]--;
    				deg[d[j]].insert(j);
    			}
    		}
    	}
    	else
    		t--;
    }
    return 0;
}