Day10-A2 DFS与连通分量专项（GESP七级风格）

参考GESP七级对DFS遍历、连通图和最少加边模型的考法。程序输出把无向图连通所需最少增加的边数。

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> g;
vector<int> vis;
void dfs(int u){
    vis[u]=1;
    for(int v:g[u]) if(!vis[v]) dfs(v);
}
int main(){
    int n,m; cin>>n>>m;
    g.assign(n+1,{}); vis.assign(n+1,0);
    while(m--){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}
    int cnt=0;
    for(int i=1;i<=n;++i) if(!vis[i]){++cnt;dfs(i);}
    cout<<cnt-1;
}

第 1 题

递归 DFS 主要借助（ ）保存未返回的调用。

{{ select(1) }}

• 哈希表
• 堆
• 队列
• 栈

第 2 题

DFS 中 vis 的首要作用是（ ）。

{{ select(2) }}

• 保存边权
• 自动排序邻接点
• 避免重复访问和无向边往返递归
• 统计入度

第 3 题

一次 dfs(s) 会访问（ ）。

{{ select(3) }}

• 所有入度为0的点
• 图中编号比 s 大的点
• 从 s 可达且此前未访问的所有顶点
• 仅 s 的直接邻点

第 4 题

邻接表 DFS 遍历全图的复杂度是（ ）。

{{ select(4) }}

• $O(2^n)$
• $O(n+m)$
• $O(\log n)$
• $O(nm^2)$

第 5 题

输入 6 3，边为 1 2、2 3、5 6，输出为（ ）。

{{ select(5) }}

• 3
• 4
• 1
• 2

第 6 题

程序输出 cnt-1 的依据是（ ）。

{{ select(6) }}

• 连接 cnt 个连通分量至少需要 cnt-1 条边
• 每个顶点都要增加一条边
• 边数总比点数少1
• DFS少访问了一个顶点

第 7 题

若 $n=5,m=0$，程序输出（ ）。

{{ select(7) }}

• 4
• 1
• 5
• 0

第 8 题

把 vis[u]=1 删除后，在含普通无向边的图上最可能出现（ ）。

{{ select(8) }}

• 拓扑序唯一
• 两个端点反复递归
• 自动得到最短路
• 邻接表变成矩阵