pat1122 Hamiltonian Cycle
사고방식: 가장자리를 기록하고 주어진 경로를 한 번 가면 된다.
코드
#include
#include
#include
#include
#include
#include
using namespace std;
typedef pair P;
int V, E, x, y;
int Q, N, s, e;
set st;
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
scanf("%d %d", &V, &E);
for (int i = 0; i < E; i++) {
scanf("%d %d", &x, &y);
st.insert(make_pair(x, y));
st.insert(make_pair(y, x));
}
scanf("%d", &Q);
while (Q--) {
scanf("%d", &N);
set sp;
for (int i = 1; i <= V; i++) {
sp.insert(i);
}
bool flag = true;
s = e = -1;
int past = -1;
for (int i = 0; i < N; i++) {
scanf("%d", &x);
if (i == 0) {s = x; past = x;}
else {
if (!st.count(make_pair(past, x))) {
flag = false;
}
past = x;
}
if (i == N-1) e = x;
if (sp.count(x)) sp.erase(x);
else if (i != N-1) flag = false;
}
if (s != e) flag = false;
if (sp.size() != 0) flag = false;
if (flag) printf("YES
");
else printf("NO
");
}
return 0;
}