基于邻接表的新顶点的增加

发布时间: 2018年11月26日 10:19   时间限制: 1000ms   内存限制: 128M

描述

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

输入

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

输出

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

样例输入1

3 21 22 342 11 240 0

样例输出1

1 22 3 13 241 22 14

1 #include
       
         2 using namespace std; 3 #define maxn 100 4  5 typedef struct node 6 { 7     int data; 8     struct node *next; 9 }Node;10 11 int main()12 {13     int n, m;14     int x, y, f;15     Node *p;16     Node *V[maxn];17     while (1)18     {19         cin >> n >> m;20         if (n == 0 && m == 0)21             break;22         for (int i = 0; i
        
         data = i;26             V[i]->next = NULL;27         }28         while (m--)29         {30             cin >> x >> y;//标准前插三部曲31             p = new Node;//建节点32             p->data = y;//赋初值33             p->next = V[x]->next;//连后继34             V[x]->next = p;//挂前驱35             p = new Node;//on the contrary36             p->data = x;37             p->next = V[y]->next;38             V[y]->next = p;39         }40         cin>>f;//new node coming 41         for (int i = 1; i <= n; i++)42         {43             cout << V[i]->data;44             p = V[i]->next;45             while (p)46             {47                 cout<<" "<
         
          data;48                 p = p->next;49             }50             cout << endl;51         }52         cout << f << endl;53     }54     return 0;55 }