【虚虚实实 欧拉图】此题链接
题意了然，用并查集来判断欧拉图
其实是用了欧拉图的性质
如果图在联通的情况下奇度顶点为2或0
#include
using namespace std;
const int maxn = 1005;
int father[maxn];
int t, n , m;
void init()
{
for(int i = 1;
i <= n;
i ++)
father[i] = i;
}
int getf(int x)
{
if(father[x] == x)
return x;
else
{
father[x] = getf(father[x]);
return father[x];
}
}
void merge(int x,int y)
{
int dx = getf(x);
int dy = getf(y);
if(dx != dy)
father[dy] = dx;
}
int main()
{
cin >> t;
while(t --)
{cin >> n >> m;
int inout[maxn];
memset(inout,0,sizeof(inout));
int t1,t2;
init();
for(int i = 1;
i <= m;
i ++)
{
cin >> t1 >> t2;
inout[t1] ++;
inout[t2] ++;
merge(t1,t2);
}
int flag = 0;
for(int i = 1;
i <= n;
i ++)
{
if(getf(i) == i)
flag ++;
}
if(flag != 1)
cout << "Xun" << endl;
else
{
int point = 0;
for(int i = 1;
i <= n;
i ++)
{
if(inout[i] % 2 == 1)
point ++;
}
if(point == 0 || point == 2)
cout << "Zhen" << endl;
else
cout << "Xun" << endl;
}
}
return 0;
}
