AcWing 1615. 哈密顿回路
原题链接
简单
作者:
leo123456
,
2020-08-27 19:25:15
,
所有人可见
,
阅读 933
//图论模拟哈密顿回路
//1:起点与终点相同
//2:每一步都有边
//3:所有点均走到
//4:查询中有n+1个点
#include<iostream>
#include<cstring>
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]])
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)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}