PP4881 有向图结点m的度（入门）

这道题要我们计算有向图里指定结点的出度、入度和度。先分清三个概念：出度是从这个结点"出发"的边的条数，入度是"指向"这个结点的边的条数，度是出度加入度。

解题思路

第一步，读懂邻接矩阵。 有向图的邻接矩阵 a[i][j] 表示"有没有从 i 指向 j 的边"，值为 1 表示有，0 表示没有。注意有向图的边有方向，所以矩阵不一定对称：a[1][2]=1 并不代表 a[2][1] 也等于 1。

第二步，找结点 m 的位置。 出度看第 m 行：第 m 行里有多少个 1，就说明 m 出发能到达多少个结点，这就是出度。入度看第 m 列：第 m 列里有多少个 1，就说明有多少个结点能到达 m，这就是入度。

第三步，用循环统计。 用两层循环读入整个矩阵后，用一个 for 循环累加第 m 行的所有数得到出度 out，再用一个 for 循环累加第 m 列的所有数得到入度 in。比如样例 n=6，m=4，第 4 行是 0 0 1 0 0 1，有两个 1，出度是 2；第 4 列是 0 1 0 0 1 0，也有两个 1，入度是 2，度就是 4。

第四步，按要求输出。 一行输出三个整数，顺序是"出度 入度 度"，中间用空格隔开。

第五步，检查边界。 题目给出 4≤n≤10，1≤m≤n，所以数组开到 12×12 就足够；注意结点的编号是从 1 开始的，数组下标也要从 1 开始用。

参考代码

// 计算有向图指定结点 m 的出度、入度和度
#include <iostream>
using namespace std;

int a[12][12];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
    int out = 0, in = 0;
    for (int j = 1; j <= n; j++) out += a[m][j]; // 第m行出边个数
    for (int i = 1; i <= n; i++) in += a[i][m];  // 第m列入边个数
    cout << out << " " << in << " " << out + in << endl;
    return 0;
}

复杂度分析

复杂度分析：读入整个矩阵需要 O(n²) 的时间，统计出度、入度各需要 O(n)，总体时间复杂度 O(n²)，空间复杂度 O(n²) 用来存矩阵。n 最大只有 10，运行起来非常快。