Problem D: [CSP-S1][程序阅读] 程序阅读9
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：42
Solved：7
Description
|
bool vis[N]; vector<int> g[N]; void dfs(int u) { vis = true; for (int v : g) if (!vis[v]) dfs(v); } int countComponents(int n) { int cnt = 0; fill(vis, vis+n, false); for (int i = 0; i < n; ++i) if (!vis[i]) dfs(i), cnt++; return cnt; } |
判断题
1. `countComponents`返回图的连通块数量。（ ）
2. 若图有自环，`dfs`会进入死循环。（ ）
3. `vis`数组需在每次`dfs`前重置。（ ）
4. 若图为森林，连通块数等于树的数量。（ ）
5. 时间复杂度为O(V+E)。（ ）
选择题
6. 对于完全图`K₄`，返回值是：
A. 1 B. 2 C. 3 D. 4
7. 若`g`为空，`dfs(u)`的递归深度是：
A. 0 B. 1 C. n D. 未定义
8. 若`vis`初始为全true，返回值是：
A. 0 B. 1 C. n D. 未定义
9. 判断两点连通需调用：
A. `dfs(u)`后检查`vis[v]` B. 直接比较`u`和`v`
C. 使用BFS D. 无法判断
10. 若图是无向图，需如何建图？
A. 每条边存两次 B. 每条边存一次
C. 无需处理 D. 无法实现