PP4883 图的邻接矩阵（入门）

这道题要求我们把一个无向图的边存进邻接矩阵，再把矩阵输出出来，是学习图论时最基础的"建图"操作。

解题思路

第一步，认识邻接矩阵。 邻接矩阵是一个 n 行 n 列的二维数组，格子 a[i][j] 表示结点 i 和 j 之间有没有边：有边填 1，没边填 0。因为是无向图，边是双向的，所以 a[i][j] 和 a[j][i] 要填相同的值。

第二步，初始化矩阵。 一开始矩阵全部是 0，表示任意两个结点之间都没有边。

第三步，读边建图。 一共 m 条边，每读一条边 x y，就把 a[x][y] 和 a[y][x] 都改成 1。比如样例第 3 条边是 2 4，那么 a[2][4]=1、a[4][2]=1。用数组存图时，可以随手在纸上面画一画：结点 1 连着 2、3、4，结点 2 连着 1、4，结点 3 连着 1、4，结点 4 连着 2、1、3，和样例输出完全吻合。

第四步，输出矩阵。 用两层循环逐行输出：外层循环 i 从 1 到 n 控制行，内层循环 j 从 1 到 n 控制列，每一行的数字之间用一个空格隔开，一行结束换行。

第五步，别忘对称赋值。 无向图最怕只写 a[x][y]=1 而忘记写 a[y][x]=1，那样图就变成有向的了，输出就会出错。

参考代码

// 输入无向图的边，建立邻接矩阵并输出
#include <iostream>
using namespace std;

int a[505][505];

int main() {
    int n, m;
    cin >> n >> m;
    for (int k = 0; k < m; k++) {
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;
        a[y][x] = 1; // 无向图对称
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (j > 1) cout << " ";
            cout << a[i][j];
        }
        cout << endl;
    }
    return 0;
}

复杂度分析

复杂度分析：建图部分读 m 条边，时间 O(m)；输出矩阵需要遍历 n² 个格子，时间 O(n²)，所以总时间复杂度 O(n²)，空间复杂度 O(n²)。n 是结点数，m 是边数。