首页 > 试题广场 >

虚虚实实

[编程题]虚虚实实
  • 热度指数：71 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
震为雷，临危不乱，亨通畅达；巽为风，柔顺伸展，厚载万物。
震卦：洊雷，震，君子以恐惧修省。一口金钟在淤泥，人人拿着当玩石，忽然一日钟悬起，响亮一声天下知。
巽卦：随风，巽，君子以申命行事。一叶孤舟落沙滩，有篙无水进退难，时逢大雨江湖溢，不用费力任往返。 
算卦先生来问你，对于每个他给出的无向图，是否存在一条路径能够经过所有边恰好一次，并且经过所有点？不需要满足最后回到起点。 

输入描述:
第一行一个数  ，表示有  组数据。对与每组数据，第一行有两个数 ，接下去  行每行两个数  描述一条无向边 。图不保证联通。


输出描述:
对于每组数据，如果存在，输出  ，否则输出  。 
示例1

输入

2
2 2
1 1
2 1
4 6
1 3
1 4
1 2
3 2
4 2
4 3

输出

Zhen
Xun

备注:



算法知识视频讲解
开通博客
头像 神崎兰子
发表于 2025-10-11 10:21:28
精华题解 虚虚实实 题解 题目描述 给定一个无向图，判断是否存在一条路径能够： 经过所有边恰好一次 经过所有点 不要求回到起点 即判断图中是否存在欧拉路径（Eulerian Path）。 核心结论 答案： 当且仅当图连通且奇度数顶点个数为 0 或 2 时，存在欧拉路径。 奇度数顶点个数为 0：存在欧拉回 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 小琢卷不动
发表于 2021-11-23 14:41:37
根据欧拉定理，我们知道当一个无向图的奇点个数为 000 或 222 时它就可以被一笔画出。 另外这个题数据不保证图是联通的，并查集判断一下就好。 想简单地说说这个遍历的方法，奇点为 000 不用说，一条入边一条出边，总有办法遍历掉，如果有两个奇点，遍历的时候就必须以其中一个为起点，另一个为终点，否则 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 -符拉迪沃斯托克-
发表于 2021-01-22 22:36:06
并查集判断连通性没得说。 一笔画问题，就是欧拉回路，只要判断度为奇数的点的个数是否为0或2即可。 附代码： #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 牛客914963476号
发表于 2020-05-09 11:44:22
https://blog.csdn.net/qq_43450892/article/details/106015821
去ta的博客 赞 (1) 回复(0) 收起
头像 计科188帅哥ZZQ
发表于 2025-04-18 23:14:57
#include<bits/stdc++.h> using namespace std; const int N =100; int ff[N]; int n,m; void init() { for(int i=0;i<=n;i++)ff[i]=i; } int find(int 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

并查集
难度：
0条回答 22浏览

热门推荐

通过挑战的用户

查看代码

相关试题

虚虚实实

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号