PP4882 无向图结点m的度（入门）

这道题是上一题"有向图结点 m 的度"的兄弟题，只不过图换成了无向图。无向图的边没有方向，所以结点的度就是和它直接相连的边的条数，统计起来更简单。

解题思路

第一步，理解无向图的邻接矩阵。 无向图里 a[i][j]=1 表示结点 i 和 j 之间有一条边。因为边没有方向，所以 a[i][j] 和 a[j][i] 一定同时为 1，整个矩阵关于对角线对称。自己和自己之间的 a[i][i] 是 0。

第二步，确定统计方法。 结点 m 的度，就是邻接矩阵第 m 行里 1 的个数。因为矩阵对称，数第 m 行和第 m 列结果是一样的，我们数第 m 行即可。

第三步，写循环统计。 读入 n 行 n 列的矩阵后，用一个 for 循环把第 m 行的 n 个数全部加起来，总和就是结点 m 的度。比如样例 n=5，m=3，第 3 行是 1 1 0 1 1，加起来正好是 4，所以输出 4。

第四步，输出结果。 只需要输出这一个整数即可。

第五步，注意读入与数组。 n 最大是 10，二维数组开 12×12 就够用；结点的编号从 1 开始，循环也从 1 到 n。

参考代码

// 计算无向图指定结点 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 cnt = 0;
    for (int j = 1; j <= n; j++) cnt += a[m][j]; // 第m行非零个数即度
    cout << cnt << endl;
    return 0;
}

复杂度分析

复杂度分析：读入矩阵需要 O(n²) 的时间，统计第 m 行需要 O(n)，总体时间复杂度 O(n²)，空间复杂度 O(n²) 用来存矩阵。n≤10，数据量非常小，程序瞬间就能算完。