第1关：基于邻接表的新顶点的增加

任务描述

给定一个无向图，在此无向图中增加一个新顶点。

编程要求

输入

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

输出

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

测试说明

平台会对你编写的代码进行测试：

测试输入：

3 2

1 2

2 3

4

2 1

1 2

4

0 0

预期输出：

1 2

2 3 1

3 2

4

1 2

2 1

4

#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MVNum 100     //最大顶点数
using namespace std;

typedef struct ArcNode {
    int adjvex;                // 邻接点域：该边所指向的顶点的位置
    int data;                  // 数据域：存储和边相关的信息
    struct ArcNode* nextarc;   // 链域：指向下一条边的指针
} ArcNode;

typedef struct VNode {
    int data;              // 顶点结点的数据域
    ArcNode* firstarc;     // 链域：指向第一条依附该顶点的边的指针
} VNode, AdjList[MVNum];   // AdjList表示邻接表类型

typedef struct ALGragh {
    AdjList vertices;
    int vexnum, arcnum;    // 图的当前顶点数和边数
} ALGragh;

int CreateUDG(ALGragh &G, int vexnum, int arcnum) {
    G.vexnum = vexnum;
    G.arcnum = arcnum;
    
    for (int i = 1; i <= vexnum; i++) {
        G.vertices[i].data = i;  // 设置顶点的数据域为顶点编号
        G.vertices[i].firstarc = NULL;  // 初始化边表为空
    }
    
    for (int i = 0; i < arcnum; i++) {
        int v1, v2;
        cin >> v1 >> v2;
        
        // 创建边结点 p1
        ArcNode* p1 = new ArcNode;
        p1->adjvex = v2;
        p1->nextarc = G.vertices[v1].firstarc;
        G.vertices[v1].firstarc = p1;
        
        // 创建边结点 p2
        ArcNode* p2 = new ArcNode;
        p2->adjvex = v1;
        p2->nextarc = G.vertices[v2].firstarc;
        G.vertices[v2].firstarc = p2;
    }
    
    return OK;
}

int InsertVex(ALGragh &G) {
    int data;
    cin >> data;
    
    G.vexnum++;
    G.vertices[G.vexnum].data = data;
    G.vertices[G.vexnum].firstarc = NULL;  // 新顶点的边表初始化为空
    
    return OK;
}

int PrintGraph(ALGragh G) {
    for (int i = 1; i <= G.vexnum; i++) {
        cout << G.vertices[i].data;
        if(G.vertices[i].firstarc)
            {
                cout<<" ";
            }
        ArcNode* p = G.vertices[i].firstarc;
        while (p) {
            cout << G.vertices[p->adjvex].data;
            if(p->nextarc)
            {
                cout<<" ";
            }
            p = p->nextarc;
        }
        cout << endl;
    }
    return OK;
}

第2关：基于邻接矩阵的新顶点的增加

任务描述

给定一个无向图，在此无向图中增加一个新顶点。

编程要求

输入

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

输出

每组数据输出n+1行。为增加顶点后的邻接矩阵。每两个数字之间用空格隔开。

#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MVNum 100     //最大顶点数
using namespace std;
typedef struct
{//图的邻接矩阵存储表示
	int vexs[MVNum];    //顶点表
	int arcs[MVNum][MVNum];    //邻接矩阵
	int vexnum,arcnum;     //图的当前点数和边数
}AMGragh;
int CreateUDN(AMGragh &G,int vexnum,int arcnum)
{//采用邻接矩阵表示法，创建无向网G
    G.vexnum=vexnum;
    G.arcnum=arcnum;
    if(G.vexnum>MVNum)
    return ERROR;
    for(int i=0;i<=G.vexnum;i++)
    {
        G.arcs[0][i]=i;
        G.arcs[i][0]=i;
    }
    for(int i=1;i<=G.vexnum;i++)
    {
        for(int j=1;j<=G.vexnum;j++)
        {
            G.arcs[i][j]=0;
        }
    }

    int h,k;

    for(int i=1;i<=G.arcnum;i++)
    {
        cin>>h>>k;
        G.arcs[h][k]=1;
        G.arcs[k][h]=1;
    }

    return OK;
}
int InsertVex(AMGragh &G)
{//在以邻接矩阵形式存储的无向图G上插入顶点
    if(G.vexnum+1>MVNum)
    return ERROR;
    int x;
    cin>>x;
    G.vexnum++;
    G.arcs[0][G.vexnum]=x;
    G.arcs[G.vexnum][0]=x;
    for(int i=1;i<=G.vexnum;i++)
    G.arcs[G.vexnum][i]=G.arcs[i][G.vexnum]=0;
    return OK;
 
 
 
}
int OutputUDN(AMGragh G)
{//输出图G
for(int i=0;i<=G.vexnum;i++)
{
    for(int j=0;j<G.vexnum;j++)
    cout<<G.arcs[i][j]<<" ";
    cout<<G.arcs[i][G.vexnum]<<endl;
}
return OK;
 }

第3关：基于邻接表的顶点的删除

任务描述

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

编程要求

输入

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

输出

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

测试说明

平台会对你编写的代码进行测试：

测试输入：

3 2

1 2

2 3

1

2 1

1 2

2

0 0

预期输出：

2 3

3 2

1

#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MVNum 100     //最大顶点数
using namespace std;
typedef struct ArcNode
{//边结点
	int adjvex;                //邻接点域：该边所指向的顶点的位置
	int data;                  //数据域：存储和边相关的信息
	struct ArcNode* nextarc;   //链域：指向下一条边的指针
}ArcNode;
typedef struct VNode
{//顶点信息
	int data;              //顶点结点的数据域
	ArcNode* firstarc;     //链域：指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum];     //AdjList表示邻接表类型
typedef struct
{//邻接表
	AdjList vertices;
	int vexnum,arcnum;    //图的当前顶点数和边数
}ALGragh;
int CreateUDG(ALGragh &G, int vexnum, int arcnum) {
    G.vexnum = vexnum;
    G.arcnum = arcnum;
    
    for (int i = 1; i <= vexnum; i++) {
        G.vertices[i].data = i;  // 设置顶点的数据域为顶点编号
        G.vertices[i].firstarc = NULL;  // 初始化边表为空
    }
    
    for (int i = 0; i < arcnum; i++) 
    {
        int v1, v2;
        cin >> v1 >> v2;
        
        // 创建边结点 p1
        ArcNode* p1 = new ArcNode;
        p1->adjvex = v2;
        p1->nextarc = G.vertices[v1].firstarc;
        G.vertices[v1].firstarc = p1;
        
        // 创建边结点 p2
        ArcNode* p2 = new ArcNode;
        p2->adjvex = v1;
        p2->nextarc = G.vertices[v2].firstarc;
        G.vertices[v2].firstarc = p2;
    }
}
void DeleteAdjList(VNode &List)
{//删除指定顶点链表上的边结点
    ArcNode* p = List.firstarc;
    ArcNode* q;

    while (p != NULL)
    {
        q = p->nextarc;
        delete p;
        p = q;
    }

    List.firstarc = NULL;
}

int DeleteVex(ALGragh &G)
{//删除G中顶点f及其相关的弧
    int f;
    cin>>f;
    //删除f顶点链表
    DeleteAdjList(G.vertices[f]);
    
    //删除其他链表中的f
    for(int i=1;i<=G.vexnum;i++)
    {
        ArcNode* p=G.vertices[i].firstarc;
        ArcNode* pre=NULL;

        while(p!=NULL)
        {
            if(p->adjvex==f) 
            {
                if(pre==NULL)
                {
                    G.vertices[i].firstarc=p->nextarc;
                    p = G.vertices[i].firstarc;
                }
                else
                {
                    pre->nextarc=p->nextarc;
                    p=p->nextarc;
                }

                delete p;
            }
            else 
            {
                pre=p;
                p=p->nextarc;
            }
        }
    }
    // 顶点数减一，边数相应减少
    G.arcnum -= G.vertices[f].firstarc != NULL ? 1 : 0;

    // 清空顶点f的数据
    G.vertices[f].data = 0;
    G.vertices[f].firstarc = NULL;

    return OK;

}
int PrintGraph(ALGragh G)
{//输出图G
   for (int i = 1; i <= G.vexnum; i++) 
   {
        if( G.vertices[i].data!=0)
        {
            cout << G.vertices[i].data;
            if(G.vertices[i].firstarc)
            {
                cout<<" ";
            }
        }
        
        ArcNode* p = G.vertices[i].firstarc;
        while (p) 
        {
            cout << G.vertices[p->adjvex].data;
            if(p->nextarc)
            {
                cout<<" ";
            }
            p = p->nextarc;
        }
        cout << endl;
    }
    return OK;
  
  
}

第4关：基于邻接矩阵的顶点的删除

任务描述

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

编程要求

输入

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

输出

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

#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MVNum 100     //最大顶点数
using namespace std;
typedef struct
{//图的邻接矩阵存储表示
	int vexs[MVNum];    //顶点表
	int arcs[MVNum][MVNum];    //邻接矩阵
	int vexnum,arcnum;     //图的当前点数和边数
}AMGragh;
int CreateUDN(AMGragh &G,int vexnum,int arcnum)
{//采用邻接矩阵表示法，创建无向网G
	G.vexnum=vexnum;
    G.arcnum=arcnum;
    //初始化行和列
    for(int i=0;i<=vexnum;i++)
    {
        G.arcs[0][i]=i;
        G.arcs[i][0]=i;
    }
    //初始化邻接矩阵
    for(int i=1;i<=vexnum;i++)
    {
        for(int j=1;j<=vexnum;j++)
        {
            G.arcs[i][j]=0;
        }
    }
    int h,k;
    for(int i=1;i<=arcnum;i++)
    {
        cin>>h>>k;
        G.arcs[h][k]=1;
        G.arcs[k][h]=1;
    }
   
   return OK;
}
int DeleteVex(AMGragh &G)
{//在以邻接矩阵形式存储的无向图G上删除顶点v
     int i,j,x;
      cin>>x;
      for(i=0;i<=G.vexnum;i++)
      for(j=x;j<G.vexnum;j++)
      G.arcs[i][j]=G.arcs[i][j+1];
      for(j=0;j<=G.vexnum;j++)
      for(i=x;i<G.vexnum;i++)
      G.arcs[i][j]=G.arcs[i+1][j];
      G.vexnum--;
      return OK;
}
int OutputUDN(AMGragh G)
{//输出图G
    for(int i=0;i<=G.vexnum;i++)
{
    for(int j=0;j<G.vexnum;j++)
    cout<<G.arcs[i][j]<<" ";
    cout<<G.arcs[i][G.vexnum]<<endl;
}
    
    return OK;
}

第5关：基于邻接表的新边的增加

任务描述

给定一个无向图，在此无向图中增加一条边。

编程要求

输入

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

输出

每组数据输出n行。为增加边后的邻接表。每两个数字之间用空格隔开。

#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MVNum 100     //最大顶点数
using namespace std;
typedef struct ArcNode
{//边结点
	int adjvex;                //邻接点域：该边所指向的顶点的位置
	int data;                  //数据域：存储和边相关的信息
	struct ArcNode* nextarc;   //链域：指向下一条边的指针
}ArcNode;
typedef struct VNode
{//顶点信息
	int data;              //顶点结点的数据域
	ArcNode *firstarc;     //链域：指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum];     //AdjList表示邻接表类型
typedef struct
{//邻接表
	AdjList vertices;
	int vexnum,arcnum;    //图的当前顶点数和边数
}ALGragh;
int CreateUDG(ALGragh &G,int vexnum,int arcnum)
{//采用邻接表表示法，创建无向图G
	G.vexnum=vexnum;
    G.arcnum=arcnum;
    //初始化表头
    for(int i=1;i<=vexnum;i++)
    {
        G.vertices[i].data=i;
        G.vertices[i].firstarc=NULL;
    }
    //创建链表
    int h,k;
    for(int i=0;i<arcnum;i++)
    {
        cin>>h>>k;
        //创建边节点h
        ArcNode *p1=new ArcNode;
        p1->adjvex=h;
        p1->nextarc=G.vertices[k].firstarc;
        G.vertices[k].firstarc=p1;
        //创建边节点k
        ArcNode *p2=new ArcNode;
        p2->adjvex=k;
        p2->nextarc=G.vertices[h].firstarc;
        G.vertices[h].firstarc=p2;
    }

    return OK;

}
int InsertArc(ALGragh &G)
{//在以邻接表形式存储的无向图G上插入边
   int f,g;
   cin>>f>>g;
   
   ArcNode *p3=new ArcNode;
        p3->adjvex=f;
        p3->nextarc=G.vertices[g].firstarc;
        G.vertices[g].firstarc=p3;
   ArcNode *p4=new ArcNode;
        p4->adjvex=g;
        p4->nextarc=G.vertices[f].firstarc;
        G.vertices[f].firstarc=p4;
    
    G.arcnum++;

    return OK;
}
int PrintGraph(ALGragh G)
{//输出图G
for (int i = 1; i <= G.vexnum; i++) {
        cout << G.vertices[i].data;
        if(G.vertices[i].firstarc)
            {
                cout<<" ";
            }
        ArcNode* p = G.vertices[i].firstarc;
        while (p) {
            cout << G.vertices[p->adjvex].data;
            if(p->nextarc)
            {
                cout<<" ";
            }
            p = p->nextarc;
        }
        cout << endl;
    }
    return OK;
  	
}

第6关：基于邻接矩阵的新边的增加

任务描述

给定一个无向图，在此无向图中增加一条边。

#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MVNum 100     //最大顶点数
using namespace std;
typedef struct
{//图的邻接矩阵存储表示
	int vexs[MVNum];    //顶点表
	int arcs[MVNum][MVNum];    //邻接矩阵
	int vexnum,arcnum;     //图的当前点数和边数
}AMGragh;
int CreateUDN(AMGragh &G,int vexnum,int arcnum)
{//采用邻接矩阵表示法，创建无向网G
    G.vexnum=vexnum;
    G.arcnum=arcnum;
    if(G.vexnum>MVNum)
    return ERROR;
    for(int i=0;i<=G.vexnum;i++)
    G.arcs[0][i]=G.arcs[i][0]=i;
    for(int i=1;i<=G.vexnum;i++)
       for(int j=1;j<=G.vexnum;j++)
       G.arcs[i][j]=0;
       int h,k;
       for(int i=1;i<=G.arcnum;i++)
       {
           cin>>h>>k;
           G.arcs[h][k]=G.arcs[k][h]=1;
       }
       return OK;
 
}
int InsertArc(AMGragh &G)
{//在以邻接矩阵形式存储的无向图G上插入边
    int x,y;
    cin>>x>>y;
    G.arcs[x][y]=G.arcs[y][x]=1;
    G.arcnum++;
    return OK;
 
}
int OutputUDN(AMGragh G)
{//输出图G
    for(int i=0;i<=G.vexnum;i++)
{
    for(int j=0;j<G.vexnum;j++)
    cout<<G.arcs[i][j]<<" ";
    cout<<G.arcs[i][G.vexnum]<<endl;
}
return OK;
 
}

第7关：基于邻接表的边的删除

任务描述

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

#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MVNum 100     //最大顶点数
using namespace std;
typedef struct ArcNode
{//边结点
	int adjvex;                //邻接点域：该边所指向的顶点的位置
	int data;                  //数据域：存储和边相关的信息
	struct ArcNode* nextarc;   //链域：指向下一条边的指针
}ArcNode;
typedef struct VNode
{//顶点信息
	int data;              //顶点结点的数据域
	ArcNode *firstarc;     //链域：指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum];     //AdjList表示邻接表类型
typedef struct
{//邻接表
	AdjList vertices;
	int vexnum,arcnum;    //图的当前顶点数和边数
}ALGragh;
int CreateUDG(ALGragh &G,int vexnum,int arcnum)
{//采用邻接表表示法，创建无向图G
	G.vexnum = vexnum;
    G.arcnum = arcnum;
    
    for (int i = 1; i <= vexnum; i++) {
        G.vertices[i].data = i;  // 设置顶点的数据域为顶点编号
        G.vertices[i].firstarc = NULL;  // 初始化边表为空
    }
    
    for (int i = 0; i < arcnum; i++) {
        int v1, v2;
        cin >> v1 >> v2;
        
        // 创建边结点 p1
        ArcNode* p1 = new ArcNode;
        p1->adjvex = v2;
        p1->nextarc = G.vertices[v1].firstarc;
        G.vertices[v1].firstarc = p1;
        
        // 创建边结点 p2
        ArcNode* p2 = new ArcNode;
        p2->adjvex = v1;
        p2->nextarc = G.vertices[v2].firstarc;
        G.vertices[v2].firstarc = p2;
    }

    return OK;
}
int DeleteArc(ALGragh &G)
{//在以邻接表形式存储的无向图G上删除边
   int f, g;
    cin >> f >> g;

    // 删除从顶点f到顶点g的边
    ArcNode *p = G.vertices[f].firstarc;
    ArcNode *pre = NULL;
    while (p != NULL && p->adjvex != g) {
        pre = p;
        p = p->nextarc;
    }
    if (p != NULL) {  // 找到边f-g
        if (pre == NULL) {
            G.vertices[f].firstarc = p->nextarc;
        } else {
            pre->nextarc = p->nextarc;
        }
        delete p;
    }

    // 删除从顶点g到顶点f的边
    p = G.vertices[g].firstarc;
    pre = NULL;
    while (p != NULL && p->adjvex != f) {
        pre = p;
        p = p->nextarc;
    }
    if (p != NULL) {  // 找到边g-f
        if (pre == NULL) {
            G.vertices[g].firstarc = p->nextarc;
        } else {
            pre->nextarc = p->nextarc;
        }
        delete p;
    }

    return OK;
}
int PrintGraph(ALGragh G)
{//输出图G
  for (int i = 1; i <= G.vexnum; i++) {
        cout << G.vertices[i].data;
        if(G.vertices[i].firstarc)
            {
                cout<<" ";
            }
        ArcNode* p = G.vertices[i].firstarc;
        while (p) {
            cout << G.vertices[p->adjvex].data;
            if(p->nextarc)
            {
                cout<<" ";
            }
            p = p->nextarc;
        }
        cout << endl;
    }
    return OK;
}

第8关：基于邻接矩阵的边的删除

任务描述

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

#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MVNum 100     //最大顶点数
using namespace std;
typedef struct
{//图的邻接矩阵存储表示
	int vexs[MVNum];    //顶点表
	int arcs[MVNum][MVNum];    //邻接矩阵
	int vexnum,arcnum;     //图的当前点数和边数
}AMGragh;
int CreateUDN(AMGragh &G,int vexnum,int arcnum)
{//采用邻接矩阵表示法，创建无向网G
	G.vexnum=vexnum;
    G.arcnum=arcnum;
    if(G.vexnum>MVNum)
    return ERROR;
    for(int i=0;i<=G.vexnum;i++)
    G.arcs[0][i]=G.arcs[i][0]=i;
    for(int i=1;i<=G.vexnum;i++)
       for(int j=1;j<=G.vexnum;j++)
       G.arcs[i][j]=0;
       int h,k;
       for(int i=1;i<=G.arcnum;i++)
       {
           cin>>h>>k;
           G.arcs[h][k]=G.arcs[k][h]=1;
       }
       return OK;
}
int DeleteArc(AMGragh &G)
{//在以邻接矩阵形式存储的无向图G上删除边
  int x,y;
    cin>>x>>y;
    G.arcs[x][y]=G.arcs[y][x]=0;
    G.arcnum--;
    return OK;
}
int OutputUDN(AMGragh G)
{//输出图G
   for(int i=0;i<=G.vexnum;i++)
  {
    for(int j=0;j<G.vexnum;j++)
    cout<<G.arcs[i][j]<<" ";
    cout<<G.arcs[i][G.vexnum]<<endl;
  }
return OK;
}