BJFU_数据结构习题_276基于邻接矩阵的新顶点的增加

欢迎登录北京林业大学OJ系统

http://www.bjfuacm.com

276基于邻接矩阵的新顶点的增加

描述

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

输入

多组数据，每组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

4

2 1

1 2

4

0 0

输出样例 1

0 1 2 3 4

1 0 1 0 0

2 1 0 1 0

3 0 1 0 0

4 0 0 0 0

0 1 2 4

1 0 1 0

2 1 0 0

4 0 0 0

#include<iostream>
using namespace std;
#define OK 0
#define ERROR -1
#define MAX 100
typedef struct AMGragh 
{
	int vexnum;
 	int arcnum;
	int vexs[MAX][MAX];
}AMGragh;
int CreateUDN(AMGragh &G,int vexnum,int arcnum)
{
	G.vexnum=vexnum;
	G.arcnum=arcnum;
	if(G.vexnum>MAX)
    	return ERROR;
  	for(int i=0;i<=G.vexnum;i++)
		G.vexs[0][i]=G.vexs[i][0]=i;
	for(int i=1;i<=G.vexnum;i++)
		for(int j=1;j<=G.vexnum;j++)
			G.vexs[i][j]=0;
	int h,k;
    for(int i=1;i<=G.arcnum;i++)
    {
		cin>>h>>k;
	    G.vexs[h][k]=G.vexs[k][h]=1;
    }
	return OK;
}
int InsertVex(AMGragh &G)
{
  	if(G.vexnum+1>MAX)
    	return ERROR;
  	int x;
  	cin>>x;
	G.vexnum++;
	G.vexs[0][G.vexnum]=G.vexs[G.vexnum][0]=x;
	for(int i=1;i<=G.vexnum;i++)
		G.vexs[G.vexnum][i]=G.vexs[i][G.vexnum]=0;
	return OK;  
}
int OutputUDN(AMGragh G)
{
	for(int i=0;i<=G.vexnum;i++)
	{
		for(int j=0;j<G.vexnum;j++)
			cout<<G.vexs[i][j]<<" ";	
		cout<<G.vexs[i][G.vexnum]<<endl;	
	}
	return OK;
}
int main()
{
	int n,m;
	while(cin>>n>>m&&m!=0&&n!=0)
	{
		AMGragh G;
      	CreateUDN(G,n,m);
      	InsertVex(G);
      	OutputUDN(G);
	}
	return 0;	
}