文章目錄

• • 題目分析
  • 題目鏈接

題目分析

分析
哈密頓回路：從1個(gè)點(diǎn)出發(fā)，經(jīng)過所有點(diǎn)一次，然后回到起點(diǎn)。

四個(gè)特點(diǎn)： 1）回路必須包含n+1個(gè)點(diǎn)；2）回路是個(gè)環(huán)，第一點(diǎn)和最后一個(gè)點(diǎn)相等；3）回路中相鄰兩個(gè)點(diǎn)之間都有邊；4）原來的每個(gè)點(diǎn)都走到。

ac代碼

#include<bits/stdc++.h> using namespace std; const int N = 210;int n, m; bool g[N][N],st[N]; int nodes[N*2];//判斷是否是哈密頓回路 bool check(int cnt){if(nodes[0] != nodes[cnt-1] || cnt != n+1) return false;memset(st, 0 ,sizeof st);for(int i = 0; i< cnt -1; i++){st[nodes[i]] =true;if(!g[nodes[i]][nodes[i+1]]) //相鄰兩個(gè)點(diǎn)必須有邊return false;}for(int i=1 ;i<=n; i++) //每個(gè)點(diǎn)都走到if(!st[i]) return false;return true; }int main(){cin >> n >> m;while(m--){int a, b;cin >> a >> b;g[a][b] = g[b][a] =true;}int k ;cin >> k;while(k--){int cnt;cin >> cnt;for(int i=0 ;i< cnt; i++) cin>> nodes[i]; //讀入回路的點(diǎn)if(check(cnt)) cout<<"YES"<<endl;else cout<<"NO"<<endl;} }

題目鏈接

PAT甲級(jí)1122 Hamiltonian Cycle
https://www.acwing.com/problem/content/1617/

總結(jié)

以上是生活随笔為你收集整理的PAT甲级1122 Hamiltonian Cycle：[C++题解] 图论、模拟的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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