著名的“漢密爾頓（Hamilton）回路問題”是要找一個(gè)能遍歷圖中所有頂點(diǎn)的簡(jiǎn)單回路（即每個(gè)頂點(diǎn)只訪問 1 次）。本題就要求你判斷任一給定的回路是否漢密爾頓回路。

輸入格式：

首先第一行給出兩個(gè)正整數(shù)：無向圖中頂點(diǎn)數(shù)?N（2<N≤200）和邊數(shù)?M。隨后?M?行，每行給出一條邊的兩個(gè)端點(diǎn)，格式為“頂點(diǎn)1 頂點(diǎn)2”，其中頂點(diǎn)從 1 到N?編號(hào)。再下一行給出一個(gè)正整數(shù)?K，是待檢驗(yàn)的回路的條數(shù)。隨后?K?行，每行給出一條待檢回路，格式為：

n?V?1???V?2?????V?n??

其中?n?是回路中的頂點(diǎn)數(shù)，V?i???是路徑上的頂點(diǎn)編號(hào)。

輸出格式：

對(duì)每條待檢回路，如果是漢密爾頓回路，就在一行中輸出"YES"，否則輸出"NO"。

輸入樣例：

6 10 6 2 3 4 1 5 2 5 3 1 4 1 1 6 6 3 1 2 4 5 6 7 5 1 4 3 6 2 5 6 5 1 4 3 6 2 9 6 2 1 6 3 4 5 2 6 4 1 2 5 1 7 6 1 3 4 5 2 6 7 6 1 2 5 4 3 1

輸出樣例：

YES NO NO NO YES NO

?ac代碼

#include<iostream> using namespace std; int main() {int m,n;cin>>n>>m;int v1,v2,v;int mp[201][201]={0};for(int i=1;i<=n;i++){mp[i][i] = 1;}for(int i=1;i<=m;i++){cin>>v1>>v2;mp[v1][v2]=mp[v2][v1]=1;}int num,k,vis;cin>>m;for(int i=0;i<m;i++){cin>>k;int begin;cin>>begin;vis = begin;int flag = 1;int visited[210]={0};for(int j=1;j<k;j++){cin>>num;if(visited[num])flag = 0;if(mp[vis][num]==0)flag = 0;visited[num]=1;vis = num;}if(k!=n+1)flag = 0;if(vis != begin)flag = 0;if(flag) cout<<"YES"<<endl;else cout<<"NO"<<endl; }return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的汉密尔顿回路的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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