CSP-J 入门级 · CSP 2022 入门级第一轮 第 9 题

考虑由 $N$ 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素。

拿到题先想：有向图怎么才算‘连通’？把边看成无向边时能跑通整个图，那最省边的做法是什么？画个环就懂了，N个点围一圈正好N条边，对应邻接矩阵里N个非零元素。

很多同学会下意识套用无向图的经验，觉得N个点连通最少N-1条边，直接选A。这是把‘有向连通’和‘无向连通’混为一谈了。还有人选D，以为邻接矩阵全是1，或者把‘连通’理解成强连通（任意两点互相可达），那确实需要更多边，但题只说了‘连通’，默认指弱连通。记住：有向图里只要别把边看成无向边就断开了就行，画个单向环就够了，所以底限就是N。

这道题考查什么：图的基本概念——有向连通图的边数下界，以及邻接矩阵中非零元素与边的对应关系。

概念讲人话：有向连通图（题目没特指强连通，默认指弱连通）的意思是，如果你把图中所有的有向边都当成无向边来看，整个图是连通的，也就是任意两个点之间至少有一条路径（方向可以不管）。邻接矩阵是N×N的方阵，A[i][j]=1表示存在从i到j的有向边，所以矩阵里非零元素的个数，正好等于图中边的数量。

命题人怎么挖坑：出题人故意把‘有向’和‘连通’放在一起，就是想看你有没有区分‘弱连通’和‘强连通’，以及会不会把无向图的结论N-1直接套过来。很多学生看到‘连通’就想到树，树最少边是N-1，于是选A；或者看到‘有向’就想到必须双向可达，以为要N条边甚至更多，可能选C或D。这些陷阱都源于对‘有向连通’定义的理解偏差。

思考心法：拿到题先想——N个点要连在一起，最省边的做法是什么？如果是无向图，一条线串起来就行，N-1条边。但这是有向图，方向不能反，所以得保证每个点都有至少一条出边指向下一个点，形成一条‘单向回路’：v1→v2→v3→…→vN→v1。这样N个点、N条边，把方向忽略后就是一个圈，显然是连通的。能不能更少？假设只有N-1条边，根据图论常识，N个点N-1条边要想连通，必须是一棵树（无环），但树在有向意义下，至少有一个点没有出边（叶子），那这个点就无法到达其他点，图就不连通了。所以N-1条边不够，最少就是N条边。

具体怎么算：N条边对应邻接矩阵里N个非零元素（每条有向边恰好对应一个A[i][j]=1），因此答案就是N。

避坑：千万别选A（N-1），那是无向连通图的下界；也别选C或D，那是把‘连通’误读成‘强连通’或者认为矩阵要全1。记住：有向连通图最少边数就是N，对应矩阵最少N个非零元素。

考频与趋势：在题库的‘图的存储’分类下，这道题是CSP入门级仅有的1道相关真题（2022年），整体‘图的存储’考频不高，但‘图的基本概念’是高频考点，历年共281题，尤其在2023-2026年爆发式增长（2023年36题、2024年61题、2025年58题、2026年71题），说明初赛越来越重视基础概念的辨析。

预测：基于近年趋势，未来入门级和普及级初赛仍会高频出现‘有向/无向连通’‘邻接矩阵/邻接表非零元素’这类概念辨析题，可能会换表述（如‘最少非零元素’变成‘最少1的位置’），但核心还是考弱连通与强连通的区别，以及边数与矩阵元素的对应关系。暂无足够依据预测具体年份或题型变化，建议把‘有向连通图最少边数=N’这条结论刻在脑子里，遇到类似变形题都能秒杀。