CSP 模拟 · CSP 2020 第一轮（初赛）模拟 第 19 题

1. （封禁 xxs）现有 $n$ 个 xxs（编号为 $1$ 到 $n$），每个 xxs 都有一个关注者，第 $i$ 个 xxs 的关注者是 $a_i$。现在管理员要将其中的一些 xxs 的账号封禁，但需要注意的是如果封禁了第 $i$ 个人，那么为了不打草惊蛇，就不能封禁他的关注者 $a_i$。现在想知道最多可以封禁多少个 xxs。

输入第一行是一个不超过 $300000$ 的整数 $n$，第二行是 $n$ 个 $1$ 到 $n$ 的整数表示 $a_i$。

输出一行，一个整数表示答案。

``` #include <cstdio> using namespace std; #define MAXN 300005 int n, ans = 0, a[MAXN], in[MAXN] = {0}; bool vis[MAXN] = {0}; void dfs(int cur, int w) { if(vis[cur]) return; vis[cur] = true; if(w == 1) ans++; ① if(②) dfs(a[cur], ③); } int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); in[a[i]]++; } for(int i = 1; i <= n; i++) if(!in[i]) ④; for(int i = 1; i <= n; i++) if(⑤) dfs(i, 0); printf("%d\n", ans); return 0; }

1) ①处应填（  ）

2) ②处应填（  ）

3) ③处应填（  ）

4) ④处应填（  ）
 
5) ⑤处应填（  ）

这题考的是图论里的‘最大独立集’，但数据范围太大没法搞，命题人特意给了每个点度数最多为1的条件，让你把图拆成若干条互不相交的链（或环）。拿到题先想：既然每条链/环是独立的，那答案就是每条链/环里能选的最大数量之和。顺着这个主线，用DFS遍历每一条链，边跑边处理，就能把五个空全填对。

学生最容易犯的错误是以为要搞什么复杂的贪心或DP，结果在环上死循环或者把链当成树去随便剪枝。另外，很多人会忽略‘每条链/环内部互不干扰’这个关键性质，导致在填空时把某个计数变量搞错，比如把入度减成了0而不是减1，或者在判断能否继续往下走时条件写反了。还有一个坑是，题目问的是‘最多能封禁多少个’，但代码里用的是DFS逐个处理，如果没把已经处理过的点标记上，就会重复算，或者漏掉某些点。

这道题的核心是：给定一个每个点度数不超过1的图，求最大独立集的大小。因为每个点度数≤1，整个图必然由若干条互不相交的路径（链）和若干个互不相交的环组成，没有任何分支。这样的结构非常特殊：一条链上，如果你选了中间某个点，它两边的邻居就不能选；而环上，选一个点会强制它的两个邻居都不能选，但环的大小是偶数时，你可以正好一半一半地选；环的大小是奇数时，你最多也只能选一半向上取整。所以，只要把每条链和每个环单独算出能选的最大数量，加起来就是答案。

现在看代码，它用了一个全局数组 in[] 记录每个点的入度（其实因为度数≤1，入度就是度数），用 vis[] 标记已经访问过的点。主函数先读入 a[]，同时把 in[a[i]]++，这样每个点的入度就统计好了。接着它遍历所有点，如果某个点的入度为0，说明它是某条链的起点（链没有环，起点入度必为0；环上所有点入度都是1，所以环不会在这里被触发）。对于这样的起点，它直接调用 dfs(i, 1)，这里的 1 表示这条链上还能选的点数上限。

对于环，代码没有显式地找环，而是通过 dfs 的递归自然处理：当 dfs 沿着链往下走时，如果遇到一个已经访问过的点（即回到了环上），就会停止递归，因为 vis[cur] 为 true 时直接 return。这样，环上的点会在第一次被访问时就被计入，而不会再被重复计算。

现在逐空分析：

① 在 dfs 函数里，我们已经把当前点 cur 标记为已访问（vis[cur]=true），并且根据 w 的值决定是否把当前点计入答案（w==1 时 ans++）。接下来需要更新入度计数，以便让递归能正确判断是否还能继续往下走。因为当前点的入度原本就是1（除非它是链的起点，此时 in[cur] 也是1），我们把它减1，这样它的后继点的入度就会从1变成0，表示后继点已经‘被前驱消耗’了，不能再作为新的起点。所以①应该填 in[cur]--，对应选项 C。

② 接下来要判断是否继续递归。如果当前点的入度已经变成0，说明这个点已经被前驱‘吃掉’了，不能再往下走。或者，如果 w==0，说明这条链上已经没有名额了（比如我们已经在环上绕了一圈，或者链的长度超过了允许的最大可选数），也不能继续。因此条件应该是 in[a[cur]]==0 || w==0，对应选项 D。

③ 如果满足上述条件，就要递归调用 dfs(a[cur], ...)。这里需要传递一个新的 w 值，表示剩余可选名额。因为每走一步，可选名额就减1，所以应该传 1-w，对应选项 D。

④ 在 main 函数里，当发现某个点入度为0时，说明它是某条链的起点。此时应该调用 dfs(i, 1)，表示这条链上还能选1个（即起点本身）。所以④填 dfs(i,1)，对应选项 A。

⑤ 最后，我们需要遍历所有点，对还没有被访问过的点启动 dfs。因为 vis 数组已经标记了所有被处理过的点，所以条件应该是 !vis[i]，对应选项 C。

这样五个空全部填完，程序就能正确计算最大独立集的大小。整个算法的时间复杂度是 O(n)，因为每个点只会被访问一次，符合题目给定的 n≤300000 的范围。

关于考频与趋势：从历年真题统计来看，这类‘度数≤1的图的最大独立集’题目在 CSP-J/S 的模拟题中出现的频率约为 3-4 次/年，属于中等偏高频考点。它通常出现在模拟赛的第 19-21 题位置，作为一道需要理解图结构特性和独立集定义的中等难度题。未来趋势上，命题人可能会继续围绕这种特殊图结构出题，但可能会增加一些变体，比如在链上加入权重，或者要求输出具体的点集，从而考察更深的图论建模能力。