鏈接：https://www.nowcoder.com/acm/contest/86/D
來源：牛客網(wǎng)

題目描述

震為雷，臨危不亂，亨通暢達；巽為風，柔順伸展，厚載萬物。
震卦：洊雷，震，君子以恐懼修省。一口金鐘在淤泥，人人拿著當玩石，忽然一日鐘懸起，響亮一聲天下知。
巽卦：隨風，巽，君子以申命行事。一葉孤舟落沙灘，有篙無水進退難，時逢大雨江湖溢，不用費力任往返。? 算卦先生來問你，對于每個他給出的無向圖，是否存在一條路徑能夠經(jīng)過所有邊恰好一次，并且經(jīng)過所有點？不需要滿足最后回到起點。?

輸入描述:

第一行一個數(shù) ，表示有 組數(shù)據(jù)。對與每組數(shù)據(jù)，第一行有兩個數(shù) ，接下去 行每行兩個數(shù) 描述一條無向邊 。圖不保證聯(lián)通。

輸出描述:

對于每組數(shù)據(jù)，如果存在，輸出 ?，否則輸出 。? 示例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. 使用 歐拉圖的充要條件，即 連通圖存在歐拉回路當且僅當每個頂點的度為偶數(shù)。 連通圖存在歐拉通路當且僅當存在 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 //統(tǒng)計奇數(shù)定點的個數(shù)，如果是 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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/TianyuSu/p/9398438.html

總結(jié)

以上是生活随笔為你收集整理的牛客小白月赛2 D 虚虚实实 【欧拉图】【连通图】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。