题目描述

震为雷，临危不乱，亨通畅达；巽为风，柔顺伸展，厚载万物。
震卦：洊雷，震，君子以恐惧修省。一口金钟在淤泥，人人拿着当玩石，忽然一日钟悬起，响亮一声天下知。
巽卦：随风，巽，君子以申命行事。一叶孤舟落沙滩，有篙无水进退难，时逢大雨江湖溢，不用费力任往返。

输入描述:

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

输出描述:

对于每组数据，如果存在，输出 ，否则输出 。

输入

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

输出

Zhen
Xun

思路

首先用并查集判断图连通， 对于所有的点如果自己是自己的祖先的点只有一个的话，那么这个图就是连通图。

欧拉回路的判定是: 如果一个连通图的奇数度的点的个数不超过2个,如果成立就是欧拉回路，否则就不是

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define inf 0x3f3f3f3f
#define x1 hpc_x1
#define y1 hpc_y1
typedef long long ll;
const double eps=1e-5;
const int N=1e5+10;
int pre[N],deg[N];
int n,m;
void init()
{for(int i=1; i<=n; i++)pre[i]=i;mem(deg,0);
}
int find(int x)
{return x==pre[x]?x:pre[x]=find(pre[x]);
}
void mix(int x,int y)
{int fx=find(x),fy=find(y);if(fx!=fy)pre[fy]=fx;
}
int main()
{int t,u,v;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);init();for(int i=1; i<=m; i++){scanf("%d%d",&u,&v);mix(u,v);deg[u]++,deg[v]++;}int sum=0,res=0;for(int i=1; i<=n; i++){if(i==find(i))sum++;if(deg[i]&1)res++;}if(sum!=1)puts("Xun");else{if(res<=2)puts("Zhen");elseputs("Xun");}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！