个人练习-PAT甲级-1122 Hamiltonian Cycle

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805351814119424

题目大意：给出一个图，然后给出若干path，如果满足哈密尔顿圈输出YES，不满足输出NO

思路：建立数据结构，扫描就行。注意每一条path，即使扫描到中间就可以判断不满足了，也要将其扫描完。不然后面一条path不好扫描。所以干脆先将一条path先完整读进来再说。

第三个if条件实际上可以去掉，因为到最后一个点时，如果不是起始点，那么肯定是不满足的；如果是起始点，那么这是第二次碰到了，也会返回false的。不过加上的话在中间就可以判断出不满足直接return，稍微快一点。

    for (int j = 1; j < n; j++) {
    v1 = path[j-1];v2 = path[j];if (!mat[v1][v2])return false;if (known[v2])return false;if (v2 == path[0] && j != n-1)return false;known[v2] = true;}

完整代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>using namespace std;int N, M, K;
bool mat[201][201];bool Judge() {
    bool flag = true;int n, v1, v2;scanf("%d", &n);vector<int> path(n, 0);vector<bool>  known(N+1, false);for (int j = 0; j < n; j++)scanf("%d", &path[j]);for (int j = 1; j < n; j++) {
    v1 = path[j-1];v2 = path[j];if (!mat[v1][v2])return false;if (known[v2])return false;if (v2 == path[0] && j != n-1)return false;known[v2] = true;}for (int v = 1; v <= N; v++) {
    if (!known[v])return false;}return true;
}int main() {
    scanf("%d %d", &N, &M);for (int i = 0; i < M; i++) {
    int v1, v2;scanf("%d %d", &v1, &v2);mat[v2][v1] = mat[v1][v2] = true;}scanf("%d", &K);for (int i = 0; i < K; i++) {
    if (Judge())printf("YES\n");elseprintf("NO\n");}return 0;
}