CSP-J 2021 第一轮 第 6 题：无向连通图删边成树

题目

对于有 $n$ 个顶点、$m$ 条边的无向连通图 $(m>n)$，需要删掉（  ）条边才能使其成为一棵树。

选项

• A. $n-1$
• B. $m-n$
• C. $m-n-1$
• D. $m-n+1$

答案

D

题解

答案是 D．\(m-n+1\)。

有 \(n\) 个顶点的树恰好有 \(n-1\) 条边。原图有 \(m\) 条边，所以需要删除 \[ m-(n-1)=m-n+1 \] 条边。

注意不能随意删：每次删掉环上的一条边，就不会破坏连通性；一直删到没有环，剩下的就是一棵树。