提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

1122 Hamiltonian Cycle

cycle
2023-09-11 14:22:44 时间

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), 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 V​1​​ V​2​​ ... V​n​​

where n is the number of vertices in the list, and V​i​​'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

题意：

　　给出一个图，判断所给的节点是不是哈密尔顿路径。

思路：

　　1. 首先判断所给的路径是不是连通。

　　2. 判断是不是给出了图中的全部结点。

　　3. 判断路径的起点和终点是不是相同。

Code：

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int main() {
 6     int n, m, k;
 7     cin >> n >> m;
 8     vector<vector<int> > grap(n + 1, vector<int>(n + 1, 0));
 9     int v1, v2;
10     for (int i = 0; i < m; ++i) {
11         cin >> v1 >> v2;
12         grap[v1][v2] = 1;
13         grap[v2][v1] = 1;
14     }
15     cin >> k;
16     int num;
17     set<int> s;
18     bool isHamiltonianCycle;
19     for (int i = 0; i < k; ++i) {
20         cin >> num;
21         vector<int> v(num);
22         s.clear();
23         isHamiltonianCycle = true;
24         for (int j = 0; j < num; ++j) {
25             cin >> v[j];
26             s.insert(v[j]);
27         }
28         if (num != n + 1 || s.size() != n)
29             isHamiltonianCycle = false;
30         else {
31             for (int j = 1; j < num; ++j) {
32                 if (grap[v[j]][v[j - 1]] == 0) {
33                     isHamiltonianCycle = false;
34                     break;
35                 }
36             }
37         }
38         if (v[0] != v[num - 1]) isHamiltonianCycle = false;
39         if (isHamiltonianCycle)
40             cout << "YES" << endl;
41         else
42             cout << "NO" << endl;
43     }
44     return 0;
45 }

 

相关文章