1287: 我是用来防AK的
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:292
解决:294
题目描述
如标题所示,此题是用来防AK。
哈密顿图(哈密尔顿图)(英语:Hamiltonian path,或Traceable path)是一个无向图,由天文学家哈密顿提出,由指定的起点前往指定的终点,途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图,闭合的哈密顿路径称作哈密顿回路(Hamiltonian cycle),含有图中所有顶点的路径称作哈密顿路径。
哈密顿图的由来:天文学家哈密顿(William Rowan Hamilton) 提出,在一个有多个城市的地图网络中,寻找一条从给定的起点到给定的终点沿 途恰好经过所有其他城市一次的路径。
从图中的任意一点出发,路途中经过图中每一个结点当且仅当一次,则成为哈密顿回路。
要满足两个条件:
⒈封闭的环
⒉是一个连通图,且图中任意两点可达
经过图(有向图或无向图)中所有顶点一次且仅一次的通路称为哈密顿通路。
经过图中所有顶点一次且仅一次的回路称为哈密顿回路。
具有哈密顿回路的图称为哈密顿图,具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。
平凡图是哈密顿图。
现在有一个10000个点的无向图,上面有很多很多很多条边(我也不知道有多少个很多),问你这个图是不是哈密顿图,如果是哈密顿图,请在1秒内找出它所有的回路。
输入
没有输入
输出
只需输出“I can AK!”(不带引号)即可。
样例输入 复制
无
样例输出 复制
I can AK!