Responsive image

问题 E: 第5关:基于邻接矩阵的新顶点的增加

问题 E: 第5关:基于邻接矩阵的新顶点的增加

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 17
[提交][状态][讨论版][命题人:]

题目描述

给定一个无向图,在此无向图中增加一个新顶点。
#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;  //超出最大顶点数则结束函数
int i,j;
for(i=0;i<=G.vexnum;i++)     //依次输入顶点信息
        G.vexs[i]=i;
    for(i=0;i<=G.vexnum;i++)    //初始化邻接矩阵,边的权值均置为0
    {
        for(j=0;j<=G.vexnum;j++)
G.arcs[i][j]=0;
    }
int h,k;                    //一条边依附的两个顶点h和k
    for(i=0;i<G.arcnum;i++)      //构造邻接矩阵
    {
cin>>h>>k;
        G.arcs[h-1][k-1]=1;           //边的权值置为1
        G.arcs[k-1][h-1]=1;           //对称边的权值也置为1
    }
return OK;
}
int InsertVex(AMGragh &G)
{//在以邻接矩阵形式存储的无向图G上插入顶点
/**************begin************/
  







  
    /**************end************/
}
int OutputUDN(AMGragh G)
{//输出图G
    int i,j;
for(i=0;i<=G.vexnum;i++)      //输出第一行顶点表
    {
        if(i!=G.vexnum)
            cout<<G.vexs[i]<<" ";
        else
            cout<<G.vexs[i]<<endl;
    }
    for(i=0;i<G.vexnum;i++)    //输出其余各行
    {
        cout<<G.vexs[i+1]<<" ";   //先输出顶点
        for(j=0;j<G.vexnum;j++)
        {
            if(j!=G.vexnum-1)
                cout<<G.arcs[i][j]<<" ";
            else
                cout<<G.arcs[i][j]<<endl;
        }
    }
return OK;
}
int main()
{
int n,m;                  //n个顶点和m条边
while(cin>>n>>m)
{
if(n==0&&m==0) break;     //输入结束标志
AMGragh G;
      CreateUDN(G,n,m);    //采用邻接矩阵表示法,创建无向网G
      InsertVex(G);        //在以邻接矩阵形式存储的无向图G上插入顶点
      OutputUDN(G);       //输出图G
}
return 0;
}

输入描述

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

样例输出

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

提示


组合提交代码,你需要提交



int InsertVex(AMGragh &G)

{//在以邻接矩阵形式存储的无向图G上插入顶点

/**************begin************/

  















  

    /**************end************/

}





[提交][状态]
ACM算法攻关部