PAT 1122. 哈密顿回路
原题链接
简单
作者:
YAX_AC
,
2024-11-16 13:35:21
,
所有人可见
,
阅读 2
//vertex n.顶点 vertex in a graph图中的顶点 the number of vertices顶点数量
//the number of edges in an undirected graph. 无向图中的边数。
//Vi's are the vertices on a path Vi是路径中经过的点
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 210;
//Hamiltonian Cycle哈密顿回路
//1.起点与终点相同
//2.每一步都有边
//3.所有均走到
//4.总共点数n+1,起点两次,其余点一次
int n,m;
bool g[N][N],st[N];
int nodes[N*2];
bool check(int cnt)
{
//判断起点与终点是否相同,和总点数是否为n+1
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]])//没有边
return false;
}
//判断每个点是否都走到
for(int i = 1; i<=n; i++)
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];
if(check(cnt)) puts("YES");
else puts("NO");
}
return 0;
}