15518虚虚实实

题目描述 

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

算卦先生来问你，对于每个他给出的无向图，是否存在一条路径能够经过所有边恰好一次，并且经过所有点？不需要满足最后回到起点。 

输入描述:

第一行一个数 TT ，表示有 TT 组数据。对与每组数据，第一行有两个数 n,mn,m，接下去 mm 行每行两个数 u,vu,v 描述一条无向边 (u,v)(u,v)。图不保证联通。

输出描述:

对于每组数据，如果存在，输出 \texttt{"Zhen"}"Zhen" ，否则输出 \texttt{"Xun"}"Xun" 。 

示例1

输入

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

输出

Zhen Xun

备注:

1<=T<=200

2<=n<=30

1<=m<=n*(n-1)/2

解题思路：

题目中问到是否存在一条路径能够经过所有的边 恰好一次并经过所有的点。

      

通过上面的两个图 我们可以发现，当度为1的点有一个或者是零个的时候就满足题目的要求。。。

但是当我们看到 这个图的时候就会发现，我们上面的 那个结论不完整。。。我们如何改变这个图可以让他满足题目要求呢？？？

当我们去掉1---->3,1---->2之间的联系时，， 就会满足条件。。。

我们会发现，，要想满足题目要求，，我们要使得我们所建立的这个无向图中，，度为奇数的个数为1个或者0个时，就存在一条 路径可以恰好通过所有的边一次，并且还可以经过所有的 顶点。。

所以我们可以使用并查集来判断图的 连通性，，然后 记录每个点的度（入度+出度）的个数，来进行判断。

 当度为奇数的个数为1个或者0个时，输出“Zhen”，否则，，输出"Xun"

#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; int f[50]; int du[50]; int book[50][50]; int getf(int v) { if(f[v]==v) return v; else { f[v]=getf(f[v]); return f[v]; } } void merge(int x,int y) { int t1=getf(x); int t2=getf(y); if(t1!=t2) f[t2]=t1; } int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); memset(du,0,sizeof(du)); memset(book,0,sizeof(book)); for(int i=1;i<=n;i++) f[i]=i; int u,v; for(int i=0;i<m;i++) { scanf("%d%d",&u,&v); if(u==v) continue; merge(u,v); du[u]++; du[v]++; } int num=0; int cnt=0; // for(int i=1;i<=n;i++) // printf("%d>>>>\n",du[i]); for(int i=1;i<=n;i++) { if(f[i]==i) num++; } if(num>1) { printf("Xun\n"); } else { for(int i=1;i<=n;i++) if(du[i]%2==1) cnt++; if(cnt==0||cnt==2) printf("Zhen\n"); else printf("Xun\n"); } } return 0; }