描述
给定一个无向图,在此无向图中增加一条边。
输入
多组数据,每组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;
}