4007-基于邻接表的新边的增加(C++,附思路)
2021/11/28 11:11:47
本文主要是介绍4007-基于邻接表的新边的增加(C++,附思路),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
描述
给定一个无向图,在此无向图中增加一条边。
输入
多组数据,每组m+2行。第一行有两个数字n和m,代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个数字h和k,代表边依附的两个顶点。第m+2行有两个数字f和g,代表增加的边所依附的两个顶点。当n和m都等于0时,输入结束。
输出
每组数据输出n行。为增加边后的邻接表。每两个数字之间用空格隔开。
输入样例 1
3 2 1 2 2 3 3 1 3 1 1 2 1 3 0 0
输出样例 1
1 3 2 2 3 1 3 1 2 1 3 2 2 1 3 1
思路:
做题顺序:4003-4005-4007,邻接表的详解在我的这篇文章里,创建,遍历有疑问的同学可以看这篇~4003基于邻接表的新顶点的增加(C++,附详细解析)_鹤天寻的博客-CSDN博客https://blog.csdn.net/qq_54416938/article/details/121582300?spm=1001.2014.3001.5501
关于本题”加新边“的思路,本质上还是普通的前插法插入过程,只不过arcnum多了1而已,所以直接在插入的时候设置循环的次数比正常次数多1就可以了,不必另做复制粘贴的工作。
#include<iostream> #include<string> #include<algorithm> #include<vector> #include<set> #include<map> using namespace std; typedef struct LNode { int data; struct LNode* next; }LNode, * linklist; typedef struct { int vexnum; int arcnum; linklist VList; }ALGraph; void Create(ALGraph& alg, int n, int m) { alg.vexnum = n; alg.arcnum = m; alg.VList = new LNode[n + 1]; for (int i = 1; i <= n; i++) { alg.VList[i].data = i; alg.VList[i].next = NULL; } int h, k; for (int i = 0; i <= m; i++) { cin >> h >> k; linklist p = new LNode, q = new LNode; p->data = h; p->next = alg.VList[k].next; alg.VList[k].next = p; q->data = k; q->next = alg.VList[h].next; alg.VList[h].next = q; } } void Show(ALGraph alg) { for (int i = 1; i <= alg.vexnum; i++) { linklist p = &alg.VList[i]; while (p) { cout << p->data; if (p->next) cout << ' '; p = p->next; } cout << endl; } } int main() { int m, n; while (cin >> n >> m && m != 0 && n != 0) { ALGraph a; Create(a, n, m); Show(a); } return 0; }
这篇关于4007-基于邻接表的新边的增加(C++,附思路)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain