4005基于邻接表的顶点的删除(C++,附思路）

描述

给定一个无向图，在此无向图中删除一个顶点。

输入

多组数据，每组m+2行。第一行有两个数字n和m，代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个数字h和k，代表边依附的两个顶点。第m+2行有一个数字f，代表删除的顶点编号。当n和m都等于0时，输入结束。

输出

每组数据输出n-1行。为删除顶点后的邻接表。每两个数字之间用空格隔开。

输入样例 1 

3 2
1 2
2 3
1
2 1
1 2
2
0 0
           

输出样例 1

2 3
3 2
1      

思路：

做题顺序：4003-4005，邻接表的详解在我的这篇文章里，创建，遍历有疑问的同学可以看这篇~4003基于邻接表的新顶点的增加（C++，附详细解析）_鹤天寻的博客-CSDN博客

https://blog.csdn.net/qq_54416938/article/details/121582300?spm=1001.2014.3001.5501

关于本题的思路，同样是“假删除”，用一个指针遍历邻接表，跳过输入要删除的节点即可，注意这里节点出现的位置可能在邻接表表头，或者是其他节点的链接里，不要忽略了后者！

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
using namespace std;

typedef struct LNode
{
	int vex;
	struct LNode* next;
}LNode, * linklist;
typedef struct
{
	linklist VList;
	int vexnum;
	int arcnum;
}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].vex = 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->vex = h;
		p->next = alg.VList[k].next;
		alg.VList[k].next = p;
		q->vex = k;
		q->next = alg.VList[h].next;
		alg.VList[h].next = q;
	}
}
void Show(ALGraph alg)
{
	int del;
	cin >> del;
	for (int i = 1; i <= alg.vexnum; i++)
	{
		if (i == del)
			continue;
		else
		{
			linklist p = &alg.VList[i];
			while (p->next)
			{
				if (p->vex == del)
					p = p->next;
				if (p)
				{
					cout << p->vex;
					if (p->next && p->next->vex != del)
						cout << ' ';
					p = p->next;
				}
			}
			if (p && p->vex != del)
				cout << p->vex << endl;
			else
				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;
}