PAT甲级-1122 Hamiltonian Cycle

题目

题目大意

给定一个图和几组顶点，判断每组顶点是否能构成一个哈密顿回路。

知识点

哈密顿回路满足几点要求：构成一个封闭环，并且经过所有顶点，每个顶点经过一次。

即满足第一个顶点值和最后一个顶点值相等；只有一个重复的顶点；非重复顶点数有n（图的总顶点数）个；连通图。

set集合可存放互不重复的数据，并且自动从小到大排序。

思路

图用一个邻接矩阵来表示，数据结构是二维数组。然后按照哈密顿回路的构成要求模拟即可。计算非重复顶点数目可以将其放入set集合中，用.size()即可。

代码

#include <iostream>
#include <vector>
#include <set>
using namespace std;int n, m, k;
int g[201][201] = {0};int main(){cin >> n >> m;for (int i = 0; i < m; i++){int v1, v2;cin >> v1 >> v2;g[v1][v2] = g[v2][v1] = 1;}cin >> k;for (int i = 0; i < k; i++){int num;cin >> num;vector<int> v(num);set<int> st;bool flag1 = false, flag2 = true;for (int i = 0; i < num; i++){int vi;cin >> vi;v[i] = vi;st.insert(vi);}if (st.size() == n && n == num - 1 && v[0] == v[num - 1]){flag1 = true;}  // 环，包括全部节点，只有一个重复节点，首尾节点相同for (int i = 0; i < num - 1; i++){if (g[v[i]][v[i + 1]] == 0){flag2 = false;}  // 所有的节点是否都能连通}flag1 && flag2 ? cout << "YES" << endl : cout << "NO" << endl;}return 0;
}