C-Graphic Game_2022年江西省大学生程序设计竞赛（正式赛） (nowcoder.com)
Topic describes eightCirno被推荐了一个游戏，她决定今天和Daiyousei一起玩。最初，有一个具有2 × n个顶点和m条边的图。在每一个转弯，Cirno和Daiyousei都必须选择一个不同的顶点。两个朝鲜顶点的度数必须相同。然后，Cirno和Daiyousei将把它们从图中删除。现在Cirno想知道有没有办法从给定的图中移除所有的顶点。如果存在，请给出xmpEnter the description:第一行包含两个整数，分别表示n和m。(1 s n, m s 106)对于下面的m行，每行包含两个整数u和v，代表一个边。l(1Su vs 2xn)它限制了没有多边和自循环。Output description:如果没有办法从给定的图中删除所有的顶点，输出引号)。(没有否则，输出n行，每行包含两个整数，表示在此删除的顶点chosenl转弯。如果有很多方法，输出其中任何一种。
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
示例1
输入
复制
2 4 2 3 1 2 4 2 3 4
输出
复制
4 3 2 1
示例2
输入
复制
5 12 7 5 1 7 10 4 6 7 3 4 5 4 10 8 9 1 3 7 6 10 2 4 2 8
输出
复制
7 4 5 3 2 6 10 8 1 9
题解:
首先我们应该明白为什么,肯定可以删完,
证明:
图会有这三种情况
1.一些孤立点
两两配对,最多会有一个孤立点
2.一些树
叶子节点一直两两配对,最多会有一个孤立点
3.一些环上连了一些边
如果有多个这样的延申边,一直两两配对度数唯一的点,最多会有一个延申边
最简情况,只要是这种,最后最多有一个孤立点
环上不相邻的点也可能互相连接
(1),没有延申边的两个点相连,度数各加一,还是可以
(2).有延申边的点和无延申边的点相连,度数各加一,环上一定会有不是这两个点的度数相等,切完这些点,就变成
最简情况,只要是这种,最后最多有一个孤立点
这种情况
以上所有的情况可能会留下一些孤立点,由于点数为2*n,我们是两两配对的,所以剩下的点也只可能是偶数
最后模拟割点即可,每次找度数想等的点,无论咋割都可以
具体实现在代码中体现
(像set这种类型容器尽量不要开太大,很容易炸内存)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
using namespace std;
vector<int> p[2000050];
int du[2000050];
set <int> f[1000050];
void solve()
{
int n,m;
scanf("%d%d",&n,&m);
n *= 2;
for(int i = 1;i <= m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
du[a] ++;
du[b] ++;
p[a].push_back(b);
p[b].push_back(a);
}
for(int i = 1;i <= n;i++)
{
f[du[i]].insert(i);
}
int t = m;
while(t >= 0)
{
if(f[t].size() >= 2)
{
int x = *f[t].begin();
f[t].erase(f[t].begin());
int y = *f[t].begin();
f[t].erase(f[t].begin());
printf("%d %d\n",x,y);
// cout << x <<" "<<y <<"\n";
du[x] = 0,du[y] = 0;
for(auto ne:p[x])
{
if(du[ne] > 0)
{
f[du[ne]].erase(ne);
du[ne] --;
f[du[ne]].insert(ne);
}
}
for(auto ne:p[y])
{
if(du[ne] > 0)
{
f[du[ne]].erase(ne);
du[ne]--;
f[du[ne]].insert(ne);
}
}
}
else
{
t--;
}
}
}
signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
int t = 1;
// cin >> t;
while(t--)
{
solve();
}
}
