所设计的程序能够通过编译,给定包含10个结点且存在哈密尔顿回路的简单图G,顶点集合为{1,2,......,10},已知边集,判断它是否为平面图。首先输入两个正整数 N 和 M,分别表示图G的顶点数和边数。紧接着的 M行,每行是用空格隔开的两个正整数u 和v ,表示对应图的一条边 (u,v), 输入的数据保证所有边都仅出现一次。输出YES代表是平面图,NO代表不是平面图。Dev-c++5.11c语言代码

时间: 2024-02-18 16:05:50 浏览: 29
好的,根据您的要求,我可以为您提供一个在Dev-C++ 5.11下编写的程序来判断这个图是否为平面图。以下是程序的实现代码: ``` #include <iostream> #include <cstring> using namespace std; const int N = 15, M = 150; int n, m; int h[N], e[M], ne[M], idx; bool st[N][N]; // 用来存储边是否存在 int q[N], cnt[N]; // q存储每个点的度数,cnt表示当前已经加入的点的数量 void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx ++ ; } bool dfs(int u, int depth) { if (depth == n) return true; // 找到了哈密尔顿回路,说明一定是平面图 for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (!st[u][j]) // 如果边(u, j)不存在 { st[u][j] = st[j][u] = true; // 加入边(u, j) if (dfs(j, depth + 1)) return true; st[u][j] = st[j][u] = false; // 回溯 } } return false; } int main() { cin >> n >> m; memset(h, -1, sizeof h); // 初始化邻接表 while (m -- ) { int a, b; cin >> a >> b; add(a, b); add(b, a); // 无向图添加两条边 } for (int i = 1; i <= n; i ++ ) q[i] = i; do { int tt = 0; for (int i = 0; i < n; i ++ ) // 模拟加点的过程 { int t = q[i]; cnt[tt ++ ] = t; for (int j = 0; j < tt - 1; j ++ ) if (st[t][cnt[j]]) // 如果点t与已经加入的点cnt[j]之间有边 goto next; // 不符合条件,直接跳到下一个排列 } memset(st, false, sizeof st); // 重置边的状态 if (dfs(q[0], 1)) // 从第一个点开始搜索哈密尔顿回路 { cout << "YES" << endl; return 0; } next: ; } while (next_permutation(q + 1, q + n + 1)); // 枚举所有排列 cout << "NO" << endl; return 0; } ``` 程序的大致思路与前面提供的程序相同,只是在使用next_permutation函数时需要稍微修改一下参数。由于数组下标从0开始,所以在调用next_permutation函数时需要将q数组的起始位置调整为q+1,终止位置调整为q+n+1。 希望这个程序能够满足您的需求,如果有任何疑问,请随时与我联系。

相关推荐

最新推荐

recommend-type

定时器产生延时1秒程序设计

实现功能:定时器产生延时1秒程序 使用芯片:STC15F104E 晶振:12MHZ 波特率:9600 编译环境:Keil
recommend-type

python程序需要编译吗

不过它是针对特定CPU体系的,这些目标代码只能在特定平台执行,如果这个程序需要在另外一种 CPU 上面运行,这个代码就必须重新编译。 它不具备可移植性,但是执行速度快,C、C++这类语言属于编译型语言。 而解释型...
recommend-type

表驱动LL(1)语法分析程序.docx

(2)所开发的程序可适用于不同的文法和任意输入串,且能判断该文法是否为LL(1)文法。 (3)对输入的任意符号串,所编制的语法分析程序应能正确判断此串是否为文法的句子(句型分析),并要求输出分析过程。 1.3使用的...
recommend-type

编译原理实验二——算符优先分析法设计与实现

用算符优先分析方法设计一个分析解释程序,对输入的赋值语句、输出语句、清除语句进行词法分析、语法分析、表达式求值并存储于指定变量中;若存在错误,提示错误相关信息。
recommend-type

实验一 简单的词法设计——DFA模拟程序.docx

通过实验教学,加深学生对所学的关于编译的理论知识的理解,增强学生对所学知识的综合应用能力,并通过实践达到对所学的知识进行验证。通过对DFA模拟程序实验,使学生掌握词法分析的实现技术,及具体实现方法。通过...
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

优化MATLAB分段函数绘制:提升效率,绘制更快速

![优化MATLAB分段函数绘制:提升效率,绘制更快速](https://ucc.alicdn.com/pic/developer-ecology/666d2a4198c6409c9694db36397539c1.png?x-oss-process=image/resize,s_500,m_lfit) # 1. MATLAB分段函数绘制概述** 分段函数绘制是一种常用的技术,用于可视化不同区间内具有不同数学表达式的函数。在MATLAB中,分段函数可以通过使用if-else语句或switch-case语句来实现。 **绘制过程** MATLAB分段函数绘制的过程通常包括以下步骤: 1.
recommend-type

SDN如何实现简易防火墙

SDN可以通过控制器来实现简易防火墙。具体步骤如下: 1. 定义防火墙规则:在控制器上定义防火墙规则,例如禁止某些IP地址或端口访问,或者只允许来自特定IP地址或端口的流量通过。 2. 获取流量信息:SDN交换机会将流量信息发送给控制器。控制器可以根据防火墙规则对流量进行过滤。 3. 过滤流量:控制器根据防火墙规则对流量进行过滤,满足规则的流量可以通过,不满足规则的流量则被阻止。 4. 配置交换机:控制器根据防火墙规则配置交换机,只允许通过满足规则的流量,不满足规则的流量则被阻止。 需要注意的是,这种简易防火墙并不能完全保护网络安全,只能起到一定的防护作用,对于更严格的安全要求,需要
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。