nyoj 42-一笔画问题 (欧拉图 && 并查集)
2024-10-06 12:20:28
42-一笔画问题
内存限制:64MB
时间限制:3000ms
Special Judge: No
accepted:10
submit:25
题目描述:
zyc从小就比较喜欢玩一些小游戏,其中就包括画一笔画,他想请你帮他写一个程序,判断一个图是否能够用一笔画下来。
规定,所有的边都只能画一次,不能重复画。
输入描述:
第一行只有一个正整数N(N<=10)表示测试数据的组数。
每组测试数据的第一行有两个正整数P,Q(P<=1000,Q<=2000),分别表示这个画中有多少个顶点和多少条连线。(点的编号从1到P)
随后的Q行,每行有两个正整数A,B(0<A,B<P),表示编号为A和B的两点之间有连线。
输出描述:
如果存在符合条件的连线,则输出"Yes",
如果不存在符合条件的连线,输出"No"。
样例输入:
复制
2
4 3
1 2
1 3
1 4
4 5
1 2
2 3
1 3
1 4
3 4
样例输出:
No
Yes 分析:
①、要想一笔画成就要满足在同一个集合(通过:“并查集”判断是否是在同一个集合)
②、在一个集合的前提下通过判断奇点个数是否为0(欧拉图)、2(半欧拉图)就可以判断是否可以一笔画成 核心代码(并查集模板):
void my_init()
{
for(int i = ; i <= n; ++ i)
pre[i] = i;
} int my_find(int x)
{
int n = x;
while(n != pre[n])
n = pre[n];
int i = x, j;
while(pre[i] != n)
{
j = pre[i];
pre[i] = n;
i = j;
}
return n;
} void my_join(int a, int b)
{
int n1 = my_find(a), n2 = my_find(b);
if(n1 != n2)
pre[n1] = n2;
}
C/C++代码实现(AC):
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <stack>
#include <map>
#include <queue>
#include <set> using namespace std;
const int MAXN = ;
int pre[MAXN], n, m, flag1, flag2, cnt, node[MAXN], cnt2; void my_init()
{
for(int i = ; i <= n; ++ i)
pre[i] = i;
} int my_find(int x)
{
int n = x;
while(n != pre[n])
n = pre[n];
int i = x, j;
while(pre[i] != n)
{
j = pre[i];
pre[i] = n;
i = j;
}
return n;
} void my_join(int a, int b)
{
int n1 = my_find(a), n2 = my_find(b);
if(n1 != n2)
pre[n1] = n2;
} int main()
{ int t;
scanf("%d", &t);
while(t --)
{
flag1 = , flag2 = , cnt = , cnt2 = ;
scanf("%d%d", &n, &m);
memset(node, , sizeof(node));
my_init();
for(int i = ; i < m; ++ i)
{
int a, b;
scanf("%d%d", &a, &b);
my_join(a, b);
node[a] ++;
node[b] ++;
}
for(int i = ; i <= n; ++ i)
{
if(pre[i] == i)
{
cnt ++;
if(cnt == )
flag1 = ;
}
if(node[i]&) cnt2 ++;
}
if(cnt2 != && cnt2 != ) flag2 = ;
if(!flag1 && !flag2) printf("Yes\n");
else printf("No\n");
}
return ;
}
最新文章
- SQLAlchemy一对多总结
- mybatis mapper association collection
- 20145302张薇 GDB调试汇编堆栈过程分析
- 全国各地电信DNS服务器地址
- Ubuntu设置目录的读写权限(Linux命令chmod 777 dirName)
- QT的父子Widget之间消息的传递(如果子类没有accept或ignore该事件,则该事件会被传递给其父亲——Qlabel与QPushButton的处理就不一样)
- Android学习笔记--AlertDialog应用
- jquery跨域访问解决方案(转)
- php这样实现伪静态
- java中Set类接口的用法
- Eclipse中代码整体左移,右移快捷键
- javascript:面向对象和常见内置对象及操作
- Asp.net Core认证和授权:JWT认证和授权
- vscode vue代码提示错误
- 小技巧css解决移动端ios不兼容position:fixed属性,无需插件
- 记录片宇宙之the secret of the sun
- UVALive 6916 Punching Robot dp
- sql server FCI and always on
- html 画出矩形,鼠标弹起,矩形消失
- oracle逐步学习总结之oracle分页查询(基础三)