【例66.1】 图论入门

解题思路

邻接矩阵非零表示存在一条有向边，数值大小是权重而不是边数。指定点行的非零项数是出度，列的非零项数是入度，整表非零项数是总边数。

正确性说明

依题目给出的对应关系逐项处理，位置与原输入保持明确对应。每一步完成当前项的全部贡献，结束后得到所有位置或字符的目标结果。

易错点

不能把权重相加当度数或边数。

复杂度

时间O(n²)，空间O(n²)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int outDegree(const vector<vector<int>> &a, int v) {
    int c = 0;
    for (int x : a[v])
        c += x != 0;
    return c;
}
int inDegree(const vector<vector<int>> &a, int v) {
    int c = 0;
    for (auto &r : a)
        c += r[v] != 0;
    return c;
}
int edgeCount(const vector<vector<int>> &a) {
    int c = 0;
    for (auto &r : a)
        for (int x : r)
            c += x != 0;
    return c;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    m--;
    vector<vector<int>> a(n, vector<int>(n));
    for (auto &r : a)
        for (int &x : r)
            cin >> x;
    cout << m + 1 << " " << outDegree(a, m) << " " << inDegree(a, m) << "\n"
         << edgeCount(a) << "\n";
    return 0;
}