PAT甲级1122.

目录

A1122

题目

样例

输入:

6 10
6 2
3 4
1 5
2 5
3 1
4 1
1 6
6 3
1 2
4 5
6
7 5 1 4 3 6 2 5
6 5 1 4 3 6 2
9 6 2 1 6 3 4 5 2 6
4 1 2 5 1
7 6 1 3 4 5 2 6
7 6 1 2 5 4 3 1

输出:

YES
NO
NO
NO
YES
NO

思路和坑点

　　思路：
　　判断是否存在哈密顿回路，即一条包含了所有结点的回路。由此可以确定一下的情况下不是哈密顿图，如果包含的节点数不等于n+1（因为回路头尾都是同一个结点，因此总共为n+1个），则不是哈密顿图；如果给定的路径不相连也不是哈密顿回路；由于题目中保证结点不重复，所以需要判定是否每个结点都出现并且都出现一次，如果不满足也不是哈密顿图。
　　按照上述逻辑进行判定即可，其中判定结点出现并且都只出现一次，可以直接使用map去重，如果总共节点数为n+1，但是map去重后的节点数不为n，说明没有包含所有结点。

AC代码

#include<bits/stdc++.h>
using namespace std;
int G[205][205]={0};                //存放图的数据
int n,m,k;                            
void judge();
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){           //读入数据，用邻接矩阵记录图
        int a,b;
        scanf("%d%d",&a,&b);
        G[a][b]=G[b][a]=1;
    }
    scanf("%d",&k);
    for(int i=0;i<k;i++)            //判断k组需要查验的路径
        judge();
    return 0;    
}
void judge()                        //判断一组序列能不能够成一组哈密顿回路
{    
    int num,temp,pre,first;         //pre记录前一个位置的结点值,first记录第一个位置的值
    bool flag=true;
    scanf("%d",&num);
    if(num!=n+1){                   //如果元素个数不等于节点数+1，一定构不成哈密顿回路
        flag=false;
        for(int i=0;i<num;i++)      //过滤本组数据
            scanf("%d",&temp);
    }
    else{
        unordered_map<int,bool> mp; //结点去重
        scanf("%d",&pre);
        first=pre;
        mp[first]=true;             //读入、保存并标记第一个结点
        for(int i=1;i<num;i++){     //后序读入结点，判断和前一个结点是否有路径，如果存在断链，则不是哈密顿回路
            scanf("%d",&temp);
            if(G[pre][temp]==0) flag=false;
            pre=temp;
            mp[temp]=true;
        }
        if(pre!=first||mp.size()!=n)//如果首尾不同或者不包含所有结点，则不是哈密顿回路
            flag=false;
    }
    puts(flag?"YES":"NO");
}