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
NO
- 分析：就是判断是不是一个哈密顿回路（用到所有节点，围成的一个简单回路）。
- code：
#include<iostream>
#include<vector>
using namespace std;
vector<vector<int> >d;
vector<int> v;
vector<int> out;
int N;
int M;
int K;
int main()
{cin>>N>>M;v.assign(N,0);d.assign(N,v);int tmp_a=0;int tmp_b=0;for(int i=0;i<M;i++){cin>>tmp_a>>tmp_b;tmp_a--;//改成从 0开始tmp_b--;d[tmp_a][tmp_b]=1;d[tmp_b][tmp_a]=1;}cin>>K;int tmp_c;int tmp_d;int count=0;bool yn=true;for(int i=0;i<K;i++){cin>>tmp_d;count=tmp_d;tmp_a=-1;tmp_b=-1;for(int j=0;j<tmp_d;j++){count--;if(j==0){cin>>tmp_a;tmp_a--;tmp_b=tmp_a;v[tmp_a]=1;continue;}else{cin>>tmp_c;tmp_c--;if(d[tmp_b][tmp_c]==1){//访问已经访问过的if(v[tmp_c]==1){//最后一个是第一个，这是对的if(tmp_c!=tmp_a)yn=false;//没到最后一个就又访问第一个，这是错的else if(count!=0)yn=false;}elsev[tmp_c]=1;}elseyn=false;tmp_b=tmp_c;}}for(int i=0;i<N;i++){//有节点没有访问到if(v[i]==0)yn=false;v[i]=0;}//所有点都访问了if(tmp_d!=N+1)yn=false;if(yn==false)out.push_back(0);elseout.push_back(1);yn=true;}for(int i=0;i<out.size();i++){if(out.at(i)==0)cout<<"NO"<<endl;elsecout<<"YES"<<endl;}return 0;
}