牛客小白月赛2 D 虚虚实实 【欧拉图】【连通图】

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

题目描述

震为雷，临危不乱，亨通畅达；巽为风，柔顺伸展，厚载万物。
震卦：洊雷，震，君子以恐惧修省。一口金钟在淤泥，人人拿着当玩石，忽然一日钟悬起，响亮一声天下知。
巽卦：随风，巽，君子以申命行事。一叶孤舟落沙滩，有篙无水进退难，时逢大雨江湖溢，不用费力任往返。  算卦先生来问你，对于每个他给出的无向图，是否存在一条路径能够经过所有边恰好一次，并且经过所有点？不需要满足最后回到起点。 

输入描述:

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

输出描述:

对于每组数据，如果存在，输出  ，否则输出 。  示例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. 使用 欧拉图的充要条件，即 连通图存在欧拉回路当且仅当每个顶点的度为偶数。 连通图存在欧拉通路当且仅当存在 0个或2个 奇度顶点 2. 如果不是连通图则不存在题目中的路径，判断连通图有很多方法，例如 并查集，DFS，BFS，传递闭包等 传送门，本体使用了 dfs AC码： 1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 int mapp[35][35],vis[35],sum[35]; 5 int n,m; 6 void dfs(int v){ 7 vis[v]=1; 8 for(int i=1;i<=n;i++){ 9 if(mapp[v][i] && !vis[i]) 10 dfs(i); 11 } 12 } 13 int main(){ 14 int t; 15 cin>>t; 16 while(t--){ 17 memset(mapp,0,sizeof(mapp)); 18 memset(vis,0,sizeof(vis)); 19 memset(sum,0,sizeof(sum)); 20 cin>>n>>m; 21 int u,v; 22 for(int i=0;i<m;i++){ 23 cin>>u>>v; 24 mapp[u][v]=mapp[v][u]=1; 25 //计算顶点的度 26 sum[u]++;sum[v]++; 27 } 28 dfs(1); 29 bool flag = false; 30 //判断是否连通 31 for(int i=1;i<=n;i++) 32 if(!vis[i]){ 33 flag = true; 34 break; 35 } 36 if(flag) 37 cout<<"Xun"<<endl; 38 else{ 39 int cnt=0; 40 //统计奇数定点的个数，如果是 0 || 2 那么就存在欧拉通路 41 for(int i=1;i<=n;i++) 42 if(sum[i]&1) 43 cnt++; 44 if(cnt==0 || cnt==2) 45 cout<<"Zhen"<<endl; 46 else 47 cout<<"Xun"<<endl; 48 } 49 } 50 return 0; 51 }

 

转载于:https://www.cnblogs.com/TianyuSu/p/9398438.html

总结

以上是生活随笔为你收集整理的牛客小白月赛2 D 虚虚实实 【欧拉图】【连通图】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。