服装网站建设的宗旨有哪些,公司邮箱怎么在手机上登录,跨境电商网,专门做问卷的网站题目
著名的“汉密尔顿#xff08;Hamilton#xff09;回路问题”是要找一个能遍历图中所有顶点的简单回路#xff08;即每个顶点只访问 1 次#xff09;。本题就要求你判断任一给定的回路是否汉密尔顿回路。
输入格式#xff1a;
首先第一行给出两个正整数#xff1a…题目
著名的“汉密尔顿Hamilton回路问题”是要找一个能遍历图中所有顶点的简单回路即每个顶点只访问 1 次。本题就要求你判断任一给定的回路是否汉密尔顿回路。
输入格式
首先第一行给出两个正整数无向图中顶点数 N2N≤200和边数 M。随后 M 行每行给出一条边的两个端点格式为“顶点1 顶点2”其中顶点从 1 到N 编号。再下一行给出一个正整数 K是待检验的回路的条数。随后 K 行每行给出一条待检回路格式为
n V1 V2⋯ Vn
其中 n 是回路中的顶点数Vi是路径上的顶点编号。
输出格式
对每条待检回路如果是汉密尔顿回路就在一行中输出YES否则输出NO。
输入样例
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题解
#include iostream
#include vector
#include cstring
using namespace std;const int N 210;
int n, m, idx 0;
int h[N];
int e[N * N];
int ne[N * N];
bool mry[N];void add(int a, int b) {e[idx] b;ne[idx] h[a];h[a] idx;
}int main() {memset(h, -1, sizeof(h));cin n m;while (m--) {int x, y;cin x y;add(x, y);add(y, x);}int k;cin k;while (k--) {memset(mry, false, sizeof(mry));int num 1;int kk, beg, end;cin kk ;int p[kk1];for(int i1;ikk;i){cin p[i];}begp[1];endp[kk];if (kk ! n 1 || beg ! end) {cout NO endl;continue;}mry[beg] true;int be beg;for (int i 2; i kk; i) {int tempp[i];if (mry[temp] i ! kk) {cout NO endl;break;}bool f false;for (int j h[be]; j ! -1; j ne[j]) {int l e[j];if (l temp) {f true;break;}}if (!f) {cout NO endl;break;}mry[temp] true;be temp;num;}bool flag2 false;for (int i 1; i n; i) {if (!mry[i]) flag2 true;}if (num n 1 !flag2)cout YES endl;}return 0;
}
思路
建立静态链表然后按照题目给的顺序遍历搜索即可。
