题目分析

给定一个无向图，按顺序删除 $k$ 个节点，求每次删除后的连通块数量。

算法思路：逆向处理

由于正向删除难以维护连通性，采用逆向思维：

• 从全部节点被删除的状态开始
• 逆序添加节点，维护连通块数量

核心步骤

1. 预处理标记

for(int i=0; i<k; ++i) {
    scanf("%d", &a[i]);
    v[a[i]] = 1;  // 标记将被删除的节点
}

2. 初始连通块计算

计算删除所有目标节点后的连通块数量：

for(int i=0; i<n; ++i) {
    if(!v[i]) {  // 未被删除的节点
        cnt++;
        dfs(i);  // 遍历连通块
    }
}
ans[k] = cnt;  // 存储结果

3. 逆向添加节点

从最后一个删除的节点开始逆序添加：

for(int i=k-1; i>=0; --i) {
    int x = a[i];
    v[x] = 0;  // 恢复该节点
    cnt++;     // 新增一个连通块
    
    for(邻接节点 y : x的邻居) {
        if(!v[y]) {  // y未被删除
            if(x和y不在同一连通块) {
                合并连通块;
                cnt--;  // 连通块减少
            }
        }
    }
    ans[i] = cnt;  // 记录当前连通块数
}

数据结构

• 邻接表：存储图结构
• 并查集：维护连通性
• 标记数组：记录节点删除状态

复杂度分析

• 时间复杂度：$O((n+m)\alpha(n))$
  • 并查集操作近似常数时间
  • 每个节点和边被处理常数次
• 空间复杂度：$O(n+m)$

样例验证

输入：

n=8, m=13, k=5
删除顺序: 1,6,3,5,7

处理过程：

1. 初始状态（删除所有目标节点）：$1$ 个连通块
2. 添加节点 $7$：$1$ 个连通块
3. 添加节点 $5$：$2$ 个连通块
4. 添加节点 $3$：$3$ 个连通块
5. 添加节点 $6$：$3$ 个连通块
6. 添加节点 $1$：$3$ 个连通块

输出：

1
1
1
2
3
3

与样例完全一致。

算法优势

• 高效性：逆向处理避免重复计算
• 简洁性：并查集维护连通性
• 正确性：保证得到精确解

该解法通过逆向思维巧妙地将删除问题转化为添加问题，利用并查集高效维护连通块数量。