判断欧拉回路

链接：https://ac.nowcoder.com/acm/contest/86/D
来源：牛客网

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

输入描述:

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

输出描述:

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

示例1

输入

复制 2 2 2 1 1 2 1 4 6 1 3 1 4 1 2 3 2 4 2 4 3

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

输出

复制 Zhen Xun

Zhen
Xun

备注:1≤T≤200

2≤n≤30
1≤m≤n*(n−1)/2

判断欧拉回路：
1.是要连通，是所有边只能经过一次，并且要经过所有的点。所以，可以用并查集来检查无向图的连通性，
如果有不连通的，则输出“Xun”，若无向图连通，则进一步考虑，这个可以用并查集判断

2.可以想象一下，若存在一条路径能够经过所有边恰好一次，并且经过所有的点，
那么除了开头的点和结尾的点都只会出现两次，进一步向下，若开头和结尾相连（形成一个环），
则开头和结尾也会出现两次，反之，若不相连，则开头和结尾出现一次，此时只要看每个点的出现次数是否为奇数，
并算出奇数的个数cnt，若cnt=0或cnt=2，则为“Zhen”，反之，为“Xun”。

判断欧拉通路是离散数学的知识，对于无向图来说，度数为奇数的的点可以有2个或者0个，并且这两个奇点其中一个为起点另外一个为终点

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e6+100;
int degree[maxn],pre[maxn];
int n,m;
int find(int x){
    if(pre[x]==x){
        return pre[x];
    }
    else{
        pre[x]=find(pre[x]);
        return pre[x];
    }
}
void marge(int x,int y){
    int h1=find(x);
    int h2=find(y);
    if(h1!=h2){
        pre[h1]=h2;
    }
} 
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            degree[i]=0;
            pre[i]=i;
        }
        int x,y;
        for(int i=1;i<=n;i++){
            cin>>x>>y;
            merge(x,y);
            degree[x]++;
            degree[y]++; 
        }
        int cnt=0;
        for(int i=1;i<=n;i++){
            if(pre[i]==i){
                cnt++;
            }
        }
        if(cnt>1){//有不连通的 
            cout<<"Xun"<<endl;
        }
        else{
            cnt=0;
            for(int i=1;i<=n;i++){
                if(degree[i]%2){
                    cnt++;
                }
            }
            if(cnt==0||cnt==2){//环或者起点终点 
                cout<<"Zhen"<<endl;
            }
            else{
                cout<<"Xun"<<endl;
            }
        }
    }
}