描述

给定一个无向图，在此无向图中删除一条边。

输入

多组数据，每组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 2 3 1 1 2 1 2 0 0

输出样例 1

讯享网1 2 2 1 3 1 2 3

//基于邻接表的边的删除 #include <iostream> #define MVNum 100 using namespace std; typedef struct ArcNode{//边信息 int p;//顶点 ArcNode *nextarc; //下一条边 }ArcNode,*ArcList; typedef struct VNode{//顶点信息 int name;//存储顶点的代号 ArcNode *ArcList;//指向第一条依附于他的边 }VNode,AdjList[MVNum];//如果此处用链表不好随时调用某顶点的信息 typedef struct{ AdjList vertices;//图的本体 int vexnum,arcnum;//图的当前顶点数和边数 }ALGraph; void Create_V(ALGraph &G,int name){//构造顶点 输入逻辑地址 int pos=++G.vexnum; G.vertices[pos-1].name=name;//vexnum是逻辑地址，所以-1 G.vertices[pos-1].ArcList=NULL; } void Create_Arc(ALGraph &G,int h,int k){//构造边 int posh=0,posk=0; for(int i=1;i<=G.vexnum;i++){//查找左右顶点的逻辑地址 if(h==G.vertices[i-1].name) posh=i; if(k==G.vertices[i-1].name) posk=i; } if(posh*posk==0) return;//此处删去也行 题目没做要求 如果边的点不在图中 退出 ArcNode *ph=new ArcNode;//h的新邻接点 ArcNode *pk=new ArcNode;//p的新邻接点 ph->p=k;//p新邻接点的名字 ph->nextarc=G.vertices[posh-1].ArcList;//前插法 G.vertices[posh-1].ArcList=ph; pk->p=h;//h新邻接点的名字 pk->nextarc=G.vertices[posk-1].ArcList;//前插法 G.vertices[posk-1].ArcList=pk; G.arcnum++; } void Delete_Arc(ALGraph &G,int h,int k){//删除边 int ph=0; int pk=0; for(int i=1;i<=G.vexnum;i++){//查找待删除边的两顶点的逻辑地址 if(h==G.vertices[i-1].name) ph=i; if(k==G.vertices[i-1].name) pk=i; } if(G.vertices[ph-1].ArcList->p==k){//如果h第一个邻接结点就是k 则让他指向下一个并删除k ArcNode *s=G.vertices[ph-1].ArcList; G.vertices[ph-1].ArcList=G.vertices[ph-1].ArcList->nextarc; delete s; } else{//如果h第一个邻接结点不是k 则遍历寻找是k的结点 ArcNode *p=G.vertices[ph-1].ArcList; while(p->nextarc) if(p->nextarc->p==k){ ArcNode *s=p->nextarc; p->nextarc=s->nextarc; delete s; break; } } if(G.vertices[pk-1].ArcList->p==h){//如果h第一个邻接结点就是k 则让他指向下一个并删除k ArcNode *s=G.vertices[pk-1].ArcList; G.vertices[pk-1].ArcList=G.vertices[pk-1].ArcList->nextarc; delete s; } else{//如果h第一个邻接结点不是k 则遍历寻找是k的结点 ArcNode *p=G.vertices[pk-1].ArcList; while(p->nextarc) if(p->nextarc->p==h){ ArcNode *s=p->nextarc; p->nextarc=s->nextarc; delete s; break; } } G.arcnum--;//G的边数-1 } void Out_Graph(ALGraph G){//输出图 for(int i=1;i<=G.vexnum;i++){ ArcNode *p=G.vertices[i-1].ArcList; if(!p){//第一种情况，如果没有邻接点，输出名字并进入下一层循环 cout<<G.vertices[i-1].name<<endl; continue; } cout<<G.vertices[i-1].name<<" ";//第二种情况，有邻接点，输出名字+空格 while(p->nextarc){//如果下一个邻接点还有 输出邻接点名+空格 cout<<p->p<<" "; p=p->nextarc; } cout<<p->p<<endl;//输出最后一个邻接点 } } void Calculate(int m,int n){ ALGraph G; G.vexnum=G.arcnum=0; for(int i=1;i<=m;i++) Create_V(G,i);//构造前n个顶点 for(int i=1;i<=n;i++){//构造n条边 int h,k; cin>>h>>k;//输入左右顶点 Create_Arc(G,h,k);//构造边 } int del_h,del_k;//待删除边的顶点 cin>>del_h>>del_k; Delete_Arc(G,del_h,del_k);//删除顶点 Out_Graph(G);//输出图 } int main(){ int m,n; while(cin>>m>>n&&m!=0&&n!=0){//每次处理一组数据 Calculate(m,n); } return 0; }