完整程序：DFS 顺序、连通块与修改影响

无向图邻接表中的邻居均按编号升序保存。程序读入 7 个点和边 (1,2),(1,3),(2,4),(2,5),(3,6),(5,6)。完成第 1～12 题。

vector<int> g[8];
bool vis[8];
int cnt = 0, components = 0, largest = 0;

int dfs(int u) {
    vis[u] = true;
    cout << u << " ";
    int sz = 1;
    cnt++;
    for (int v : g[u])
        if (!vis[v]) sz += dfs(v);
    return sz;
}

int main() {
    // 建图后对每个 g[i] 升序排序
    for (int i = 1; i <= 7; ++i) {
        if (!vis[i]) {
            components++;
            largest = max(largest, dfs(i));
        }
    }
    cout << "|" << components << " " << cnt << " " << largest;
}

第 1 题

程序中 DFS 输出的顶点序列是什么？

{{ input(1) }}

---

第 2 题

变量 components 的最终值是多少？

{{ input(2) }}

---

第 3 题

变量 cnt 的最终值是多少？

{{ input(3) }}

---

第 4 题

变量 largest 的最终值是多少？

{{ input(4) }}

---

第 5 题

函数 dfs(u) 的返回值含义是（ ）。

{{ select(5) }}

• 从 u 启动本次搜索访问的连通块大小
• u 的度数
• 图中边数
• 从 u 到 1 的距离

---

第 6 题

孤立点 7 对应的 dfs(7) 返回多少？

{{ input(6) }}

---

第 7 题

若删除边 (5,6)，DFS 输出序列是什么？

{{ input(7) }}

---

第 8 题

若去掉 vis[u]=true，在该无向图上最可能出现（ ）。

{{ select(8) }}

• 自动得到最短路
• 沿边来回递归，无法正常结束
• 只漏掉孤立点
• 复杂度变为 $O(1)$

---

第 9 题

改变邻接表中的邻居顺序，可能改变什么？

{{ select(9) }}

• 连通块数量
• 最大连通块大小
• DFS 输出顺序
• 总结点数

---

第 10 题

邻接表实现中，整个程序的时间复杂度是（ ）。

{{ select(10) }}

• $O(1)$
• $O(\log n)$
• $O(n+m)$
• $O(nm)$

---

第 11 题

外层循环中一次新的 dfs(i) 对应（ ）。

{{ select(11) }}

• 发现一个新的连通块
• 删除一条边
• 找到一条最短路
• 完成一次二分

---

第 12 题

若只调用一次 dfs(1) 而删除外层循环，哪个点不会被访问？

{{ select(12) }}

• 3
• 5
• 6
• 7

---