PAT-1122. Hamiltonian Cycle (25)

The "Hamilton cycle PRoblem" is to find a simple cycle that contains every vertex in a graph. Such a cycle is called a "Hamiltonian cycle". In this problem, you are supposed to tell if a given cycle is a Hamiltonian cycle. Input Specification: Each input file contains one test case. For each case, the first line contains 2 positive integers N (2< N <= 200), the number of vertices, and M, the number of edges in an undirected graph. Then M lines follow, each describes an edge in the format "Vertex1 Vertex2", where the vertices are numbered from 1 to N. The next line gives a positive integer K which is the number of queries, followed by K lines of queries, each in the format: n V1 V2 ... Vn where n is the number of vertices in the list, and Vi's are the vertices on a path. Output Specification: For each query, print in a line "YES" if the path does form a Hamiltonian cycle, or "NO" if not. Sample Input: 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 Sample Output: YES NO NO NO YES

题意就是输入一个图然后在输入多行数据每一行表示一个轨迹需要分析这个轨迹是否构成哈密顿回路

哈密顿回路就是一条能够串联起图中所有点的回路如何判断呢一开始想复杂了以为这个行序列里有多条起点和终点需要把每一段起点终点相同的点有可能构成回路的线段都存到向量里最后交了一发发现其实并没有这么复杂只需判断这个行序列是不是第一个数等于最后一个数并且这之间遍历了所有的点那么就符合YES条件否则输出NO

另外一定要判断这条轨迹中彼此连边是否存在不然还让你输入那么多边干嘛？

AC code：

#include<set>
#include<map>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
	int s,e;	
};
int a[210][210];
int tre[210];
int last[210];
int main()
{
	vector<node>v;
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int s,e;
		scanf("%d%d",&s,&e);
		a[s][e]=1;
		a[e][s]=1;
	}	
	int k;
	scanf("%d",&k);
	while(k--)
	{
		int t;
		scanf("%d",&t);
		for(int i=1;i<=t;i++)scanf("%d",&tre[i]);	
		bool ver[210]={0};
		int check=n;
		bool flag=0;
		for(int i=1;i<=t;i++)
		{
			if(i>1&&a[tre[i-1]][tre[i]]!=1)break;
			if(!ver[tre[i]])
			{
				check--;
				ver[tre[i]]=1;
			}
			else if(ver[tre[i]]&&check)break;
			else if(check==0&&ver[tre[i]]&&tre[1]==tre[t]&&i==t)
			{
				flag=1;
				break;
			}
		}
		if(flag)printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

PAT-1122. Hamiltonian Cycle (25)

相关推荐