题目描述

给定一个 N 个顶点、M 条边的无向图。顶点编号为 1 到 N。
对于每个 k 从 1 到 N，我们需要解决以下问题：

我们可以执行一种操作：选择一个顶点，并删除该顶点及其所有相连的边。

问：是否可以通过重复执行上述操作，使得最终从顶点 1 出发，沿着剩余的边能够到达的顶点集合恰好是 {1, 2, …, k}？

如果可能，找出达到该状态所需的最小操作次数（即删除的顶点数量）。如果不可能，则输出 -1。

对每个 k = 1, 2, …, N 输出对应的答案。

样例

输入:
6 7
1 2
1 5
2 3
2 4
2 5
3 6
5 6

输出:
2
3
3
2
1
0

样例解释 (k=2):
目标是使得从顶点 1 能且仅能到达 {1, 2}。
原始图中，1 连接 2, 5。2 连接 1, 3, 4, 5。
为了仅保留 {1, 2}，我们需要断开所有 {1, 2} 与 {3, 4, 5, 6} 之间的连接。
边 (1, 5): 需要删除 5。
边 (2, 3): 需要删除 3。
边 (2, 4): 需要删除 4。
边 (2, 5): 需要删除 5 (已经决定删除)。
我们必须删除顶点 {3, 4, 5}。删除它们后，检查 {1, 2} 的连通性。顶点 1 和 2 之间有边 (1, 2)，它们是连通的。
因此，对于 k=2，可以通过删除 3 个顶点 {3, 4, 5} 来实现。可以证明，用少于 3 次删除无法达到目标。所以 k=2 的答案是 3。

样例解释 (k=6):
目标是使得从顶点 1 能到达 {1, 2, 3, 4, 5, 6}。原始图可能已经是连通的，如果从 1 出发就能到达所有 6 个点，则不需要删除任何顶点。在本例中，原始图是连通的，且所有点均可达，所以 k=6 的答案是 0。

算法 (并查集 + 增量构造)

$O(N + M\alpha(N))$

思路分析

1. 理解目标状态: 对于给定的 k，目标状态是：

   • 集合 $S_k = \{1, 2, \dots, k\}$ 内的顶点形成一个包含顶点 1 的连通分量。
   • 集合 $S_k$ 与集合 $O_k = \{k+1, \dots, N\}$ 之间没有任何边相连。
   • 删除的顶点数最少。

2. 必要删除: 为了满足第二个条件（分离 $S_k$ 和 $O_k$），任何在 $O_k$ 中的顶点 $v$，如果它与 $S_k$ 中的某个顶点 $u$ 在原始图中有边相连，那么顶点 $v$ 必须被删除。因为如果不删除 $v$，并且 $u$ 是从 1 可达的（在目标状态下 $S_k$ 内的点都可达），那么 $v$ 也会变得可达，违反了目标状态。

3. 不应删除: 目标状态要求 $S_k$ 中的所有顶点都从 1 可达。如果我们删除了 $S_k$ 中的任何顶点，那么这个顶点就不可达了，违反了条件。因此，我们不能删除 $S_k$ 中的任何顶点。

4. 最小删除数: 结合第 2 点和第 3 点，要达到目标状态（如果可能），我们必须且仅需删除那些满足条件的顶点 $v \in O_k$（即 $v$ 与 $S_k$ 有连接）。因此，最小删除数就是这类必须删除的顶点的数量。

5. 可行性检查: 在执行了所有必要的删除后，我们还需要检查第一个条件是否满足：集合 $S_k$ 内的顶点是否形成一个包含顶点 1 的连通分量？

6. 增量计算: 直接对每个 k 计算连通性和删除数可能效率不高。考虑当 k 从 i 增加到 i+1 时，状态如何变化。

   • 目标集合从 $S_i = \{1, \dots, i\}$ 变为 $S_{i+1} = \{1, \dots, i, i+1\}$。
   • 外部集合从 $O_i = \{i+1, \dots, N\}$ 变为 $O_{i+1} = \{i+2, \dots, N\}$。
   • 连通性: 我们需要检查 $S_{i+1}$ 是否连通。这等价于检查 $S_i$ 是否连通，并且顶点 $i+1$ 是否通过 $S_{i+1}$ 内部的边连接到了 $S_i$ 的连通分量（包含 1）。
   • 删除数: 必须删除的顶点集合从 $\{v \in O_i \mid \exists u \in S_i, (u,v) \in E\}$ 变为 $\{v’ \in O_{i+1} \mid \exists u’ \in S_{i+1}, (u’,v’) \in E\}$。
     • 当 k 变为 k+1 时，顶点 k+1 从外部集合 $O_k$ 移入了内部集合 $S_{k+1}$。
     • 如果顶点 k+1 之前是必须删除的（因为它连接到了 $S_k$），那么现在它不再需要被删除。
     • 同时，我们需要考虑顶点 k+1 的邻居。对于 k+1 的每个邻居 $j \in O_{k+1}$ (即 $j > k+1$)，如果 $j$ 之前没有连接到 $S_k$，那么现在 $j$ 连接到了 $S_{k+1}$ (通过 $k+1$)，它变成了必须删除的顶点。

7. 使用并查集 (DSU) 和计数器: 我们可以按 k 从 1 到 N 的顺序进行处理，并动态维护所需的信息。

   • DSU: 使用并查集维护 $S_k = \{1, \dots, k\}$ 内部的连通性。当我们处理到 k 时，我们将顶点 k 加入考虑范围。对于所有连接 k 和 $j < k$ 的边，我们在 DSU 中合并 k 和 j。
   • 连通性检查: 在处理完顶点 k 的所有连接到 $j < k$ 的边后，检查顶点 k 是否与顶点 1 在同一个 DSU 集合中。更进一步，检查包含顶点 1 的集合的大小是否恰好为 k。如果 dsu.size(dsu.find(1)) == k，则 $S_k$ 的连通性条件满足。
   • 删除数计数: 维护一个计数器 ans，表示当前需要删除的顶点数量。维护一个数组 deg，其中 deg[v] 记录顶点 v 有多少个邻居 $u$ 满足 $u < k$（即 $u$ 在当前的目标集合 $S_k$ 中）。
     • 初始化 ans = 0, deg 全为 0。
     • 按 k 从 1 到 N (对应 0-based 索引 i 从 0 到 N-1) 迭代：
       1. 处理顶点 i 加入 $S_{i+1}$:
          • 合并连通分量: 对于所有邻居 $j$ of $i$ 且 $j < i$，执行 dsu.merge(i, j)。
          • 更新 ans (移除 i): 如果 deg[i] > 0，说明在处理 i 之前，i 是一个外部顶点 ($i > j$) 且连接到了内部集合 $S_j$（对于某个 $j<i$)。这意味着当目标集合是 $S_j$ 时，i 是需要被删除的，并且被计入了当时的 ans。现在 i 加入了目标集合 $S_{i+1}$，它不再是需要删除的顶点，所以 ans 需要减 1。
          • 更新 ans (添加 i 的邻居): 对于所有邻居 $j$ of $i$ 且 $j > i$：
            • 增加 $j$ 的“内部邻居”计数：deg[j]++。
            • 如果 deg[j] 从 0 变为 1，意味着顶点 $j$ (它在 $O_{i+1}$ 中) 刚刚通过边 $(i, j)$ 第一次连接到了目标集合 $S_{i+1}$。因此，$j$ 现在成为了一个必须删除的顶点。将 ans 加 1。
       2. 检查可行性: 检查 dsu.size(dsu.find(0)) == i + 1 (使用 0-based 索引)。
       3. 输出结果: 如果可行，输出当前的 ans；否则输出 -1。

8. 代码细节:

   • 为了方便处理，代码使用 0-based 索引 (顶点 0 到 N-1)。
   • adj[u] 存储顶点 u 的所有邻居。
   • adj1[v] 用于存储指向顶点 v 的边 (u, v) 中的 u。这使得在处理顶点 i 时，可以方便地找到所有 $j < i$ 且与 i 相连的顶点 j 来执行 DSU 合并。注意：原始代码中 adj1 的填充方式可能依赖于输入边的顺序或 u<v 的假设。如果 adj 是标准邻接表，adj1 可以在遍历 i 时通过检查 adj[i] 中的邻居 j 是否满足 j < i 来模拟。但提供的代码似乎直接用了 adj1 来获取前驱，这需要 adj1[i] 正确存储了所有连接到 i 的 j。
   • deg[v] 准确地说，是记录了在处理到步骤 i 时，顶点 v (通常 $v > i$) 有多少个邻居 $u$ 满足 $u \le i$。
   • ans 记录的是当前有多少个顶点 $v$ ($v > i$) 满足 `deg[v] > 0$。

时间复杂度

• 图的存储和预处理：O(N + M)。
• DSU 初始化：O(N)。
• 主循环 N 次。
• 在循环的第 i 次迭代中：
  • 合并操作：涉及遍历 i 的入边（或邻居中索引小于 i 的点）。总的合并操作次数是 N-1 次成功的 merge，每次 merge 的 DSU 操作复杂度接近 O(α(N))。遍历边的总次数与 M 成正比。
  • 更新 deg 和 ans：涉及遍历 i 的出边（或邻居中索引大于 i 的点）。遍历边的总次数与 M 成正比。
  • DSU find 和 size 操作：O(α(N))。
• 总时间复杂度主要是遍历边和执行 DSU 操作，为 O(N + Mα(N))，其中 α 是反阿克曼函数，非常接近常数。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using i64 = long long; // 定义 i64 为 long long 的别名
// using u64 = unsigned long long; // 未使用
// using u32 = unsigned; // 未使用
// using u128 = unsigned __int128; // 未使用

// 并查集 (Disjoint Set Union) 结构体
struct DSU {
    std::vector<int> f, siz; // f: 父节点数组, siz: 集合大小数组

    DSU() {} // 默认构造函数
    DSU(int n) { // 带大小的构造函数
        init(n);
    }

    // 初始化并查集，大小为 n
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0); // 初始化父节点为自己 (0, 1, ..., n-1)
        siz.assign(n, 1); // 初始化每个集合大小为 1
    }

    // 查找元素 x 所在集合的根节点 (带路径压缩)
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]]; // 路径压缩
        }
        return x;
    }

    // 判断 x 和 y 是否在同一个集合
    bool same(int x, int y) {
        return find(x) == find(y);
    }

    // 合并 x 和 y 所在的集合 (按大小合并，虽然代码实现是直接合并)
    // 返回 true 如果成功合并, false 如果已在同一集合
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false; // 已经在同一集合
        }
        // 按大小合并 (代码实际未按大小，但理论上应如此)
        // if (siz[x] < siz[y]) std::swap(x, y); // 保证 x 是较大的集合 (可选优化)
        siz[x] += siz[y]; // 更新根节点 x 的大小
        f[y] = x; // 将 y 的根指向 x
        return true;
    }

    // 返回元素 x 所在集合的大小
    int size(int x) {
        return siz[find(x)];
    }
};

int main() {
    // 加速 IO
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, M; // 顶点数 N, 边数 M
    std::cin >> N >> M;

    // deg[v] 记录顶点 v 有多少个邻居 u <= i (在第 i 轮迭代时)
    std::vector<int> deg(N); 
    // adj[u] 存储 u 的所有邻居 (用于更新 deg 和 ans)
    // adj1[v] 存储所有指向 v 的邻居 u (用于 DSU 合并)
    std::vector<std::vector<int>> adj(N), adj1(N);
    int ans = 0; // 当前需要删除的顶点数

    // 读入 M 条边
    for (int i = 0; i < M; i++) {
        int u, v;
        std::cin >> u >> v;
        u--; // 转换为 0-based 索引
        v--;
        // 填充邻接表 adj 和 adj1
        adj[u].push_back(v);
        adj[v].push_back(u); // 因为是无向图，两边都加
        adj1[u].push_back(v); // adj1 也存双向，下面循环处理时会隐含 u<v 或 u>v 的关系
        adj1[v].push_back(u);
    }

    DSU dsu(N); // 初始化并查集

    // 迭代处理顶点 i = 0 到 N-1 (对应 k = 1 到 N)
    for (int i = 0; i < N; i++) {
        // 1. 合并连通分量：将 i 与所有已处理的邻居 j (j < i) 合并
        // 代码中使用 adj1[i] 遍历所有邻居 j，并在循环内判断 j<i (虽然此处未显式判断)
        // 更标准的做法是：
        // for (int j : adj[i]) { if (j < i) dsu.merge(i, j); }
        // 但原代码的逻辑是正确的，因为它依赖于迭代顺序：当处理 i 时，j < i 的 merge 已完成
        // 这里直接用 adj1 遍历所有邻居并 merge 是因为 merge 对已同集的情况无害
         for (auto j : adj1[i]) { // 遍历 i 的所有邻居 j
             // 仅当 j < i 时合并才有意义，但 merge 本身会处理同集情况
             // 实际上这里隐含了 j<i 的处理，因为 j>i 的 merge 会在后续处理 j 时发生
             // 为了构建 S_{i+1} 的连通性，我们需要连接 i 和所有 j<i 的邻居
             // 这里遍历 adj1[i] (所有邻居) 并 merge 是为了方便，因为 DSU 对同集 merge 无害
             // 且能确保所有必要的连接被建立
             dsu.merge(i, j);
         }

        // 2. 更新 ans (移除 i)：如果 i 之前是需要删除的顶点，现在不再需要
        // deg[i] > 0 意味着在处理某个 j < i 时，i 作为邻居被计数了
        if (deg[i] > 0) {
            ans--;
        }

        // 3. 更新 ans (添加 i 的邻居)：处理 i 对其后继邻居的影响
        for (auto j : adj[i]) { // 遍历 i 的所有邻居 j
            // 只关心 j > i 的情况，因为 j <= i 的已在目标集 S_{i+1} 内
             if (j > i) { // 考虑邻居 j 是否成为新的必须删除顶点
                 // deg[j]++ 记录 j 又多了一个来自 S_{i+1} 的邻居 (即 i)
                 // 如果 deg[j] 之前是 0，说明 j 首次连接到目标集，变为必须删除
                 if (deg[j]++ == 0) { 
                     ans++; // 增加需要删除的顶点计数
                 }
            }
        }

        // 4. 检查可行性并输出结果 (针对 k = i + 1)
        // 检查顶点 0 所在连通分量的大小是否等于当前目标集的大小 (i + 1)
        if (dsu.size(dsu.find(0)) != i + 1) {
            // 如果大小不符，说明 S_{i+1} 内部不连通（或者包含了不该包含的点，但这被 merge 逻辑避免了）
            // 此时对于 k = i + 1 及之后的所有 k 都不可行
            std::cout << -1 << "\n";
        } else {
            // 如果大小符合，说明 S_{i+1} 内部连通性满足
            // 输出当前计算出的最小删除数 ans
            std::cout << ans << "\n";
        }
    }

    return 0; // 程序正常结束
}