如何知道一个网站用什么建设的,网站建站ddp,在线小游戏,企石网站建设题目 题目大意
给定一个图和几组顶点#xff0c;判断每组顶点是否能构成一个哈密顿回路。
知识点
哈密顿回路满足几点要求#xff1a;构成一个封闭环#xff0c;并且经过所有顶点#xff0c;每个顶点经过一次。
即满足第一个顶点值和最后一个顶点值相等#xff1b;只有…题目 题目大意
给定一个图和几组顶点判断每组顶点是否能构成一个哈密顿回路。
知识点
哈密顿回路满足几点要求构成一个封闭环并且经过所有顶点每个顶点经过一次。
即满足第一个顶点值和最后一个顶点值相等只有一个重复的顶点非重复顶点数有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;vectorint v(num);setint 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;
}
