在无向图或有向图中，顶点的度数总和为边数的两倍，即：
而在有向图中，有一个很明显的性质就是，入度等于出度。
|
|
|
|
|
无向图度数统计 #include <iostream> using namespace std; int deg[105]; int main() { int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; deg[u]++; deg[v]++; } for (int i = 1; i <= n; i++) { cout << deg[i] << " "; } return 0; }
有向图度数统计
#include <iostream> using namespace std; int outdeg[105], indeg[105]; int main() { int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; outdeg[u]++; indeg[v]++; } for (int i = 1; i <= n; i++) { cout << outdeg[i] << " " << indeg[i] << endl; } return 0; } 图的存储（无权值）图该怎么存呢？
邻接矩阵 基础知识什么是邻接矩阵呢？所谓邻接矩阵存储结构就每个顶点用一个一维数组存储边的信息，这样所有点合起来就是用矩阵表示图中各顶点之间的邻接关系。所谓矩阵其实就是二维数组。
对于有n个顶点的图 G=(V,E) 来说，我们可以用一个 n×n 的矩阵 A 来表示 G 中各顶点的相邻关系，如果 vi 和 vj之间存在边（或弧），则 A[i][j]=1 ，否则 A[i][j]=0 。下图为有向图 G1 和无向图 G2 对应的邻接矩阵：
一个图的邻接矩阵是唯一的，矩阵的大小只与顶点个数N有关，是一个 N×N 的矩阵。前面我们已经介绍过，在无向图里，如果顶点 vi 和 vj 之间有边，则可认为顶点 vi 到 vj 有边，顶点 vj 到 vi 也有边。对应到邻接矩阵里，则有 A[i][j]=A[j][i]=1 。因此我们可以发现，无向图的邻接矩阵是一个对称矩阵。
在邻接矩阵上，我们可以直观地看出两个顶点之间是否有边（或弧），并且很容易求出每个顶点的度，入度和出度。
这里我们以 G1 为例，演示下如何利用邻接矩阵计算顶点的入度和出度。顶点的出度，即为邻接矩阵上点对应行上所有值的总和，比如顶点1出度即为0+1+1+1=3；而每个点的入度即为点对应列上所有值的总和，比如顶点3对应的入度即为1+0+0+1=2。
接下来我们就先一起学习构造和使用邻接矩阵的方法。邻接矩阵是一个由1和0构成的矩阵。处于第 i 行、第 j 列上的元素1和0分别代表顶点i到j之间存在或不存在一条又向边。
显然在构造邻接矩阵的时候，我们需要实现一个整型的二维数组。由于当前的图还是空的，因此我们还要把这个二维数组中的每个元素都初始化为0。
在构造好了一个图的结构后，我们需要把图中各边的情况对应在邻接矩阵上。实际上，这一步的实现非常简单，当从顶点x到y存在边时，我们只要把二维数组对应的位置置为1就好了。
用邻接矩阵来构建图需要如下几步，我们可以用二维数组G来表示一个图。 初始化
初始化的过程很简单，只需要把数组初始化为0即可。可以借助memset来快速地将一个数组中的所有元素都初始化为0。（其实定义成全局变量就行了……）
memset(G, 0, sizeof(G));注意，memset只能用来初始化0和 -1，并且需要加上头文件cstring。
上面的代码等价于：
for (int i = 0; i < N1; i++) { // N1 为数组第一维大小 for (int j = 0; j < N2; j++) { // N2 为数组第二维大小 G[i][j] = 0; } }当然我们平常使用邻接矩阵的时候下标只用 1 到 n 或者 0 到n−1 （这个看题目中点的编号）。
插入边如果插入一条无向边 (u,v) ，只需要
G[u][v] = 1; G[v][u] = 1;也可以写成G[u][v] = G[v][u] = 1;。
如果插入一条有向边 (u,v) ，只需要G[u][v] = 1;。