当前位置:网站首页>HDU 4337 King Arthur' S Knights it outputs a Hamiltonian circuit
HDU 4337 King Arthur' S Knights it outputs a Hamiltonian circuit
2022-07-07 03:11:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack
n integral m The article has no direction
It outputs a Hamiltonian circuit
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 155;
int n, m;
bool mp[N][N];
int S, T, top, Stack[N];
bool vis[N];
void _reverse(int l,int r) {
while (l<r)
swap(Stack[l++],Stack[r--]);
}
void expand() {
while(1) {
bool flag = 0;
for (int i=1; i<=n && false == flag; i++)
if (!vis[i] && mp[T][i])
{
Stack[top++]=i;
T=i;
flag = vis[i] = 1;
}
if (!flag) return;
}
}
void hamiltun(int Start){
memset(vis, 0, sizeof vis);
S = Start;
for(T=2; T<=n; T++) // Randomly find two adjacent nodes S and T
if (mp[S][T]) break;
top = 0;
Stack[top++]=S;
Stack[top++]=T;
vis[S] = vis[T] = true;
while (1)
{
expand(); // On the basis of them, expand a path without repeated nodes as long as possible : step 1
_reverse(0,top-1);
swap(S,T);
expand(); // On the basis of them, expand a path without repeated nodes as long as possible
int mid=0;
if (!mp[S][T]) // if S And T Not adjacent , Can construct a circuit to make a new S and T adjacent
{
// Set path S→T There are k+2 Nodes , In turn S,v1,v2…… vk and T.
// It can prove the existence of nodes vi,i∈[1,k), Satisfy vi And T adjacent , And vi+1 And S adjacent
for (int i=1; i<top-2; i++)
if (mp[Stack[i]][T] && mp[Stack[i+1]][S])
{
mid=i+1; break;
}
// Turn the original path into S→vi→T→vi+1→S, It forms a loop
_reverse(mid,top-1);
T=Stack[top-1];
}
if (top==n) break;
// Now we have a loop without repeating nodes . Suppose its length is N, Then Hamilton loop is found
// otherwise , Because the whole graph is connected , So in this loop , There must be a point adjacent to a point outside the loop
// Then disconnect the circuit from that point , It's a path back , Then follow the steps 1 Try to expand the path
for (int i = 1, j; i <= n; i++)
if (!vis[i])
{
for (j=1; j<top-1; j++)
if (mp[Stack[j]][i]) break;
if (mp[Stack[j]][i])
{
T=i; mid=j;
break;
}
}
S=Stack[mid-1];
_reverse(0,mid-1);
_reverse(mid,top-1);
Stack[top++]=T;
vis[T]=true;
}
}
int main() {
while (cin>>n>>m) {
memset(mp, 0, sizeof mp);
for (int i = 1, u, v; i <= m; i++) {
scanf("%d %d",&u, &v);
mp[u][v] = mp[v][u] = 1;
}
hamiltun(1);
for (int i = 0; i < top; i++)
printf("%d%c", Stack[i], i==top-1?'\n':' ');
}
return 0;
}
Copyright notice : This article is the original article of the blogger , Blog , Do not reprint without permission .
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/116761.html Link to the original text :https://javaforall.cn
边栏推荐
- The annual salary of general test is 15W, and the annual salary of test and development is 30w+. What is the difference between the two?
- Data analysis from the perspective of control theory
- Cocos2d-x box2d physical engine compilation settings
- SQL中删除数据
- Redis入门完整教程:客户端管理
- Household appliance industry under the "retail is king": what is the industry consensus?
- Detailed explanation of 19 dimensional integrated navigation module sinsgps in psins (initial assignment part)
- How to design interface test cases? Teach you a few tips to draft easily
- 新标杆!智慧化社会治理
- 巴比特 | 元宇宙每日必读:IP授权是NFT的破圈之路吗?它的难点在哪里?Holder该如何选择合作平台?...
猜你喜欢
Redis入門完整教程:問題定比特與優化
从 1.5 开始搭建一个微服务框架——日志追踪 traceId
Le tube MOS réalise le circuit de commutation automatique de l'alimentation principale et de l'alimentation auxiliaire, et la chute de tension "zéro", courant statique 20ua
“零售为王”下的家电产业:什么是行业共识?
知识图谱构建全流程
uniapp的表单验证
Don't you know the relationship between JSP and servlet?
杰理之播内置 flash 提示音控制播放暂停【篇】
Uniapp adaptation problem
从零安装Redis
随机推荐
PSINS中19维组合导航模块sinsgps详解(初始赋值部分)
你知道电子招标最突出的5大好处有哪些吗?
2022 information security engineer examination outline
应用程序启动速度的优化
leetcode-02(链表题)
A complete tutorial for getting started with redis: problem location and optimization
杰理之关于 DAC 输出功率问题【篇】
Analysis of USB network card sending and receiving data
Codeforces round 264 (Div. 2) C gargari and Bishop [violence]
Kubernetes source code analysis (II) -- resource
尚硅谷JVM-第一章 类加载子系统
uniapp适配问题
【基于 RT-Thread Studio的CPK-RA6M4 开发板环境搭建】
CVPR 2022 最佳论文候选 | PIP: 6个惯性传感器实现全身动捕和受力估计
The first symposium on "quantum computing + application of financial technology" was successfully held in Beijing
密码学系列之:在线证书状态协议OCSP详解
Lost in the lock world of MySQL
2022年信息安全工程师考试大纲
The 8 element positioning methods of selenium that you have to know are simple and practical
Redis入门完整教程:AOF持久化