(PAT 1122) Hamiltonian Cycle (哈密顿图)

偏执的太偏执、 2022-03-20 11:58 210阅读 0赞

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
    NO

解题思路:

判断若干条条路径是否是哈密顿回路

哈密顿回路的性质:由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。

回路中不存在环,且起点与终点一致。

首先判断给出的路径中结点的个数,如果结点个数大于或小于结点总个数,说明存在环或者有结点未遍历

然后判断结点之间的连通性,判断当前结点是否与路径中的下一个结点连通,后得出结论

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <string.h>
    using namespace std;
    int N, M, K;
    const int MAXN = 210;
    bool Gedges[MAXN][MAXN];
    bool GVisited[MAXN] = { false };
    
    int main() {
    	fill(Gedges[0], Gedges[0] + MAXN * MAXN, false);
    	scanf("%d %d", &N, &M);
    	int node1, node2;
    	for (int i = 0; i < M; ++i) {
    		scanf("%d %d", &node1, &node2);
    		Gedges[node1][node2] = true;
    		Gedges[node2][node1] = true;
    	}
    	scanf("%d", &K);
    	int num,gnode;
    	for (int i = 0; i < K; ++i) {
    		memset(GVisited, 0, MAXN);
    		vector<int> Gcircles;
    		scanf("%d", &num);
    		for (int j = 0; j < num; ++j) {
    			scanf("%d", &gnode);
    			Gcircles.push_back(gnode);
    		}
    		if (Gcircles.size() != N + 1 || Gcircles[0] != Gcircles[Gcircles.size()-1]) {
    			printf("NO\n");
    			continue;
    		}
    		bool flag = true;
    		for (int k = 0; k < Gcircles.size()-1;++k) {
    			GVisited[Gcircles[k]] = true;
    			if(k == Gcircles.size() - 2 && Gcircles[k+1] == Gcircles[0]) {
    			  if (Gedges[Gcircles[k]][Gcircles[k + 1]] == false) {
    					flag = false;
    				}
    			  break;
    			}
    			if (GVisited[Gcircles[k + 1]] == true || Gedges[Gcircles[k]][Gcircles[k + 1]] == false) {
    				flag = false;
    				break;
    			}
    		}
    		if (flag) {
    			printf("YES\n");
    		}
    		else {
    			printf("NO\n");
    		}
    	}
    
    	return 0;
    }