【题解】1122 Hamiltonian Cycle (25分)⭐⭐⭐ 【哈密顿回路】
发布日期:2021-06-29 16:13:21
浏览次数:2
分类:技术文章
本文共 1175 字,大约阅读时间需要 3 分钟。
题意:
给出一个无向图
在给出若干组路径,要求判断该路径是否为哈密顿回路题解:
我们首先需要学习一下什么是哈密顿回路:从某一点出发,经过所有点恰好一次并且回到原点的回路
题中并没有给出什么是Hamilton Cycle,我们也可以通过样例自己猜一下经验小结:
1.欧拉回路 图G中经过每条边一次并且仅一次的回路称作欧拉回路。
2.欧拉路径 图G中经过每条边一次并且仅一次的路径称作欧拉路径。 3.欧拉图 存在欧拉回路的图称为欧拉图。 4.半欧拉图 存在欧拉路径但不存在欧拉回路的图称为半欧拉图。 5.哈密顿回路:经过每个点一次并且回到起点回路转一圈后即回到原点,路径不需要
另外要小心对于MAXN的定义,输入的点可不止N个,最后一个测试点
#includeusing namespace std;#define ms(x, n) memset(x,n,sizeof(x));typedef long long LL;const int INF = 1 << 30;const int MAXN = 2010;int G[MAXN][MAXN], N, M, Q, k, v[MAXN];set vis;bool judge(){ if(v[1] != v[k] || k-1 != N || vis.size() != N) //vis==N且k-1==N说明所有节点均访问且仅访问一次 return false; for(int i = 1; i < k; ++i) if(!G[v[i]][v[i+1]]) return false; return true;}int main() { ios::sync_with_stdio(false); int a, b; cin >> N >> M; while(M--){ cin >> a >> b; G[a][b] = G[b][a] = 1; } cin >> Q; while(Q--){ cin >> k; vis.clear(); for(int i = 1; i <= k; ++i){ cin >> v[i]; vis.insert(v[i]); } if(judge()) cout << "YES\n"; else cout << "NO\n"; } return 0;}
转载地址:https://suprit.blog.csdn.net/article/details/104324746 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2024年04月15日 08时15分59秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
关系型数据库 ,nosql数据库简介
2019-04-29
Centos 7搭建NTP时间同步服务器
2019-04-29
centos7 基于rsync+inotify 实现定时备份
2019-04-29
指定IP进行 文件的分发
2019-04-29
基于http搭建本地yum仓库
2019-04-29
常规邮件基础
2019-04-29
邮件基础之 -- SMTP协议
2019-04-29
Java设计模式--责任链模式
2019-04-29
OpenCV的cvLoadImage函数
2019-04-29
OpenCV中与matlab中相对应的函数
2019-04-29
C/C++中二维数组作函数形参时,调用函数时,可传递的实参类型的小结
2019-04-29
cvGetSubRect与cvMul用法
2019-04-29
opencv图像处理梯度边缘和角点
2019-04-29
Caffe源码中blob文件分析
2019-04-29
OpenCV 图像采样 插值 几何变换
2019-04-29
图像处理-仿射变换 AffineTransform
2019-04-29
图像二值化----otsu(最大类间方差法、大津算法)
2019-04-29
图像二值化----otsu(最大类间方差法、大津算法)(二)
2019-04-29
OpenCV编程案例:使用轮廓函数检测连通区域
2019-04-29
opencv使用cvFindContours提取联通域
2019-04-29