PAT 1122

题目 ： Hamiltonian Cycle

分值 ： 25
难度 ： 中等
思路 ： 一般般
坑点 ： 一开始自作聪明，以为图信息是没有用的，结果还是需要判断是否存在通路的。

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
using namespace std;
int list [201];
int map[201][201];
int flag[201] ;
bool FLAG =true ;
int main() {
    int N, M ;
    cin >> N >> M;
    for(int i = 0 ; i< M ; i++)
    {
        int c1 ,c2 ;
        cin >> c1 >> c2 ;
        map[c1][c2] =1 ;
        map[c2][c1] = 1 ;
    }
    int K ;
    cin >> K;
    for(int i = 0 ; i< K ; i++)
    {
        FLAG =true ;
        int n ; cin >> n ;
        if(n!=N+1) FLAG =false ;
        for(int j = 0 ; j < n ; j++)
        {
            cin >> list[j] ;
            if(j!=0)
            {
                if(!map[list[j-1]][list[j]])
                    FLAG = false ;
            }
            if(j!=n-1 && flag[list[j]] == i+1 ) //之前出现过
                FLAG =false ;
            flag[ list[j] ] = i+1;
        }
        if(list[0] != list[n-1] || !FLAG)
            cout <<"NO"<<endl ;
        else
            cout <<"YES"<<endl ;

    }
}