地铁图就是一张「图」：站点是节点，线路是边。编程里用一张 n×n 的 0/1 大表记录「谁和谁直接相连」：g[i][j] = 1 表示 i 到 j 有直达边——这就是邻接矩阵，图的「座位图」。
把城市地铁图想象成一张座位图：每个站点是一个座位号（节点），两条站之间的直达线路是一条边。双向可走的线（比如友谊：你好友我、我好友你）是无向边；单行道（比如「关注」：我关注你，你没关注我）是有向边。一个节点连着几条边叫它的度——像站点的换乘线路数、一个人的好友数。邻接矩阵就是 n×n 的大表：第 i 行第 j 格 = 1 表示「i 到 j 有直达边」，否则 0。无向图里「i→j 通」必然「j→i 通」，所以矩阵对称（g[i][j] = g[j][i]）——加一条边要写两个格子，一行里的 1 的个数正好就是这个节点的度。
// 图（graph）= 节点（vertex，点）的集合 + 边（edge，线）的集合 // - 无向边：两端平等，双向可走（友谊、双向道路） // - 有向边：有方向 i → j，不能反过来（关注、单行道） // 度（无向图）：与节点直接相连的边数（好友数、线路数） // 入度/出度（有向边）：进来的边数 / 出去的边数（被关注数 / 关注数） // // 例子（地铁图，5 站，无向）：边 A-B、B-C、B-D、D-E（4 条边，5 个节点） // A — B — C // | // D // | // E // 度：deg(A)=1，deg(B)=3，deg(C)=1，deg(D)=2，deg(E)=1 // 规律：所有节点度数之和 = 2 × 边数（每条边有两个端点，各记 1 次） // 本例：1+3+1+2+1 = 8 = 2 × 4 ✓
// 邻接矩阵：n×n 的表 g[1..n][1..n] // g[i][j] = 1：i 到 j 有「直达」边 // g[i][j] = 0：没有直达边 // 规则： // - 无向图：加边 i-j → g[i][j] 和 g[j][i] 都置 1（矩阵对称） // - 有向图：加边 i→j → 只置 g[i][j]（矩阵不一定对称） // - 第 i 行 1 的个数 = i 的出度（有向）/ 度（无向） // - 第 j 列 1 的个数 = j 的入度（有向） // - 主对角线 g[i][i] = 自环（节点自己连自己，一般图为 0） // // 例子（地铁图 A-B、B-C、B-D、D-E）： // A B C D E // A [ 0 1 0 0 0 ] 行和 1 = deg(A) // B [ 1 0 1 1 0 ] 行和 3 = deg(B) // C [ 0 1 0 0 0 ] 行和 1 = deg(C) // D [ 0 1 0 0 1 ] 行和 2 = deg(D) // E [ 0 0 0 1 0 ] 行和 1 = deg(E) // 对称性：g[i][j] = g[j][i]（如 g[A][B] = g[B][A] = 1）
// 5 人朋友圈（无向图）：1=小明 2=小花 3=小强 4=小芳 5=小科 // 好友关系：小明-小花，小明-小强，小花-小芳，小芳-小科 // 边：1-2、1-3、2-4、4-5（共 4 条） // // 逐条加边（无向：对称两格都写 1）： // 边 1-2：g[1][2] = g[2][1] = 1 // 边 1-3：g[1][3] = g[3][1] = 1 // 边 2-4：g[2][4] = g[4][2] = 1 // 边 4-5：g[4][5] = g[5][4] = 1 // // 1 2 3 4 5 // 1 [ 0 1 1 0 0 ] deg(1) = 2 // 2 [ 1 0 0 1 0 ] deg(2) = 2 // 3 [ 1 0 0 0 0 ] deg(3) = 1 // 4 [ 0 1 0 0 1 ] deg(4) = 2 // 5 [ 0 0 0 1 0 ] deg(5) = 1 // 自查：1 的总数 = 8 = 2 × 4 条边 ✓；对称 ✓；主对角全 0 ✓ // 小明和小科是好友吗？g[1][5] = 0 → 不是直接好友， // 但能经中转到达：1 → 2 → 4 → 5（「直达」和「可达」是两回事！）
// 算账（int 矩阵，1 个 int = 4 字节，存 n² 格）： // n = 100： 100×100 = 1 万格 × 4B = 40 KB （轻松） // n = 1000： 100 万格 × 4B = 4 MB （可接受） // n = 5000： 2500 万格 × 4B = 100 MB （紧张） // n = 10000： 1 亿格 × 4B = 400 MB （爆炸） // // 稠密图（边多，接近 n(n-1)/2 条上界）：矩阵大部分格子是 1，没浪费 → 适合 // 稀疏图（边少，比如只有 n-1 条的链）：n² 格中只有 2(n-1) 个 1 → 大量 0 白占地方 // 例：n = 1000、m = 10 条边 → 100 万格里只有 20 个 1（0.002%） // // 权衡： // - 矩阵：查「i 到 j 有没有直达边」O(1)（直接看 g[i][j]）；空间 O(n²) // - 邻接表（下节）：只存边，空间 O(n + m)；查边要扫 i 的链表 O(度) // 结论：n 不大或图稠密 → 矩阵；n 大且边稀疏 → 邻接表
// 题目：读入 n 个节点、m 条无向边，用邻接矩阵建图，输出每个节点的度（行和）。 // 输入：第 1 行 n m；接下来 m 行每行 u v（u 与 v 之间有一条无向边）。 #include <iostream> using namespace std; int g[1005][1005]; // 邻接矩阵：g[i][j] = 1 表示 i 到 j 有直达边 int main() { int n, m; cin >> n >> m; for (int k = 1; k <= m; k++) { int u, v; cin >> u >> v; g[u][v] = 1; // 无向图：对称两格都要写 g[v][u] = 1; } // 每个节点的度 = 对应行的 1 的个数 for (int i = 1; i <= n; i++) { int deg = 0; for (int j = 1; j <= n; j++) deg += g[i][j]; cout << i << " " << deg << endl; } return 0; } // 样例：n=5, m=4；边：1 2 / 1 3 / 2 4 / 4 5 // 输出：1 2 / 2 2 / 3 1 / 4 2 / 5 1（度 = 行和，总和 8 = 2 × 4 ✓）