邻接矩阵存储有向图(详解)

时间:2021-09-17 22:41:29

邻接矩阵存储有向图

【输入描述】

  输入文件包含多组测试数据,每组测试数据描述了一个无权有向图。每组测试数据第一行为两个正整数n和m,1<=n<=100,1<=m<=500,分别表示了有向图的顶点数目和边的数目,顶点数从1开始计起。接下来有m行,每行有两个正整数,用空格隔开,分别表示一条边的起点和终点。每条边出现一次且仅一次,图中不存在自身环和重边。输入文件最后一行为0 0,表示输入数据结束。

【输出描述】:

  对输入文件的每个有向图,输出两行:第一行为n个正整数,表示每个顶点的出度;第2行也为n个正整数表示每个顶点的入度。每两个正整数之间用一个空格隔开,每行的最后一个正整数之后没有空格。

【样例输入】

7  9

1  2

2  3

2  5

2  6

3  5

4  3

5  2

5  4

6  7

0  0

【样例输出】

1  3  1  1  2  1  0

0  2  2  1  2  1  1

详解代码如下:

 1 #include<string.h> 
2 #include<stdio.h>
3 #define MAXN 100 //顶点个数最大值
4 int Edge[MAXN][MAXN]; //邻接矩阵
5 int main(){
6 int i,j; //循环变量
7 int n,m; //顶点的个数、边数
8 int u,v; //边的起点与终点
9 int od,id; //顶点的出度与入度
10 while(1)
11 {
12 scanf("%d%d",&n,&m); //读入定点个数n和边数m
13 if(n==0&&m==0) break; //输入数据结束
14 memset(Edge,0,sizeof(Edge));
15 for(i=1;i<=m;i++)
16 {
17 scanf(" %d%d",&u,&v); //读入边的起点与终点
18 Edge[u-1][v-1] = 1; //构造邻接矩阵
19 }
20 for(i=0;i<n;i++) //求各顶点的出度
21 {
22 od = 0;
23 for(j=0;j<n;j++) od+=Edge[i][j]; //累加到第i行
24 if(i==0) printf(" %d",od);
25 else printf(" %d",od);
26 }
27 printf("\n");
28 for(i=0;i<n;i++) //求各顶点的入度
29 {
30 id=0;
31
32 for(j=0;j<n;j++) id+=Edge[j][i]; //累加到第i列
33 if(i==0) printf(" %d",id);
34 else printf(" %d",id);
35 }
36 printf("\n");
37 }
38 return 0;
39 }