1122 Hamiltonian Cycle (25 分)

DFS连通分量顶点数统计 + 按序列遍历检测

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, K, cnt;
vector<int> visited(201);
vector<vector<int>> G(201, vector<int> (201));
void DFS( int v )
{
    ++cnt;
    visited[v] = 1;
    for( int i = 1; i <= N; ++i )
        if( G[v][i] && !visited[ i ] )
            DFS(i);
}
int main()
{
    scanf("%d %d", &N, &M);
    for( int i = 0, v1, v2; i < M; ++i )
    {
        scanf("%d %d", &v1, &v2);
        G[v1][v2] = G[v2][v1] = 1;
    }
    scanf("%d", &K);
    for( int i = 0, n, flag; i < K; ++i )
    {
        scanf("%d", &n);
        vector<int> seq(n);
        for( int j = 0; j < n; ++j )
            scanf("%d", &seq[j]);
        cnt = flag = 0;
        fill( visited.begin(), visited.end(), 0 );
        DFS( seq[0] );
        if( cnt != n - 1 )
            flag = 1;
        fill( visited.begin(), visited.end(), 0 );
        for( int j = 1, v = seq[0]; j < n && !flag; ++j )
            if( G[v][ seq[j] ] && !visited[ seq[j] ] )
            {
                v = seq[j];
                visited[v] = 1;
            }
            else flag = 1;
        printf("%s\n", flag ? "NO":"YES");
    }
}