Moe's CF Life

喵~ 主人，今天我们来一起看看 Codeforces 上的 1857D - Strong Vertices 这道有趣的题目吧！别看它是个图论题，其实藏着一个可爱的小秘密哦，让本喵来带你发现它！

题目大意

这道题是这样哒：

我们会得到两个长度为 n 的数组 a 和 b。然后呢，我们要根据这两个数组来构建一个有 n 个顶点的有向图。

建图的规则是：对于任意两个不同的顶点 u 和 v，如果 a_u - a_v >= b_u - b_v 这个条件成立，那么就存在一条从 u 指向 v 的有向边。

我们的任务是，找出图中所有的强顶点 (strong vertices)。一个顶点 V 被称为“强顶点”，如果从 V 出发，可以沿着有向边到达图中的所有其他顶点。

最后，我们需要输出强顶点的数量，以及所有强顶点的编号（按升序排列）。

举个例子，如果 a = [3, 1, 2, 4]，b = [4, 3, 2, 1]，那么顶点 4 就是唯一的强顶点，因为从 4 可以到达 1, 2, 3 喵。

题解方法

一看到图论，是不是有点头大，想着要不要从每个点开始做一次深度优先搜索（DFS）或者广度优先搜索（BFS）来检查它能不能到达所有其他点？喵呜~ 那样太慢啦，n 的范围可是到了 2 * 10^5 呢，O(n * (n+m)) 的复杂度肯定会超时的！

所以，我们得另辟蹊径，仔细看看那个建图的条件喵！

a_u - a_v >= b_u - b_v

这个不等式看起来有点乱，因为它同时包含了 u 和 v 的信息。我们来施展一点小小的代数魔法，把它变形一下！把和 u 相关的项都移到左边，和 v 相关的项都移到右边：

a_u - b_u >= a_v - b_v

哇！你看，这个不等式是不是瞬间变得清爽多啦？

这启发了我们，可以为每个顶点 i 定义一个新的属性值，让 c_i = a_i - b_i。这样一来，从 u到 v 存在一条边的条件就变成了超级简单的：

c_u >= c_v

也就是说，只有当一个顶点的 c 值大于或等于另一个顶点的 c 值时，才可能从前者向后者连边。

现在我们再来思考一下“强顶点”的定义。一个顶点 V 是强顶点，意味着它必须能够到达所有其他顶点 U。

如果 c_V >= c_U，那么从 V 到 U 直接就有一条边，肯定能到达。
如果 c_V < c_U 呢？从 V 能到达 U 吗？我们来想一下，如果存在一条从 V 到 U 的路径，比如 V -> W_1 -> W_2 -> ... -> U，那么根据边的定义，必然有 c_V >= c_{W_1}，c_{W_1} >= c_{W_2}，...，c_{...} >= c_U。这一系列的“大于等于”传递下来，最终必然得到 c_V >= c_U。

这说明了什么？一个顶点 V 能够到达另一个顶点 U 的充要条件就是 c_V >= c_U！

喵哈哈，真相大白啦！一个顶点 V 要成为强顶点，它必须能到达所有其他顶点 U。这就意味着，对于所有的 U（从 1 到 n），都必须满足 c_V >= c_U。

换句话说，一个顶点 V 是强顶点，当且仅当它的 c_V 值是所有 c 值中的最大值！

所以，这道题的解法就非常简单了：

计算出每个顶点 i 对应的 c_i = a_i - b_i。
找到所有 c_i 中的最大值 max_c。
遍历所有的顶点，把那些 c_i 值等于 max_c 的顶点编号收集起来。
将这些编号排序输出，就完成任务啦！

是不是超级简单？一下子从复杂的图论问题，变成了一个找数组最大值的问题了喵~

题解

下面就是实现这个思路的 C++ 代码啦，本喵加了一些注释，方便主人理解哦~

cpp

#include <iostream>
#include <vector>
#include <algorithm> // 排序需要用到
#include <climits>   // 为了使用 LLONG_MIN

// 使用 using namespace std; 可以让代码更简洁喵
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<long long> a(n);
    vector<long long> b(n);
    vector<long long> c(n);

    // 读入数组 a
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    // 读入数组 b
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

    // 计算 c[i] = a[i] - b[i]
    long long max_val = LLONG_MIN; // 初始化一个非常小的值来找最大值
    for (int i = 0; i < n; i++) {
        c[i] = a[i] - b[i];
        if (c[i] > max_val) {
            max_val = c[i];
        }
    }

    // 找出所有 c[i] 等于 max_val 的顶点
    vector<int> ans;
    for (int i = 0; i < n; i++) {
        if (c[i] == max_val) {
            // 题目中的顶点编号是 1-indexed，而我们的数组是 0-indexed
            ans.push_back(i + 1);
        }
    }

    // 输出答案
    cout << ans.size() << '\n';
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << (i == ans.size() - 1 ? "" : " ");
    }
    cout << '\n';
}

int main() {
    // 这两行是为了加速 C++ 的输入输出，是个好习惯喵
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

注意：题目给出的示例代码将计算 c 数组和找最大值的过程合并了，也是一种很高效的写法。这里为了讲解清晰，我把步骤分开了，但核心思想是一样的。

知识点介绍

这道题虽然简单，但背后蕴含的思维方式非常重要哦！

问题转化 (Problem Transformation) 这是解决本题最核心的技巧！我们将一个看似复杂的图论邻接关系 a_u - a_v >= b_u - b_v，通过简单的移项，转化为了一个非常直观的大小关系 c_u >= c_v。这使得问题的本质从“图的连通性”变成了“数组元素的大小比较”。在算法竞赛中，学会简化和转化问题，往往是解题的关键一步。
图论基本概念 (Graph Theory Basics) 虽然我们最后没有用复杂的图论算法，但理解题目的图论背景是必需的。
- 有向图 (Directed Graph)：边是有方向的图，从 u 到 v 的边和从 v 到 u 的边是不同的。
- 路径 (Path)：图中从一个顶点到另一个顶点经过的边的序列。
- 可达性 (Reachability)：如果存在从顶点 u 到顶点 v 的路径，则称 v 是从 u 可达的。本题中的“强顶点”就是要求该顶点对所有其他顶点都可达。
贪心思想 (Greedy Approach) 我们的解法可以看作是一种贪心。为了能到达尽可能多的其他顶点，我们直觉上应该选择“最强”的顶点。而这里的“强”恰好就被我们量化为了 c_i = a_i - b_i 的值。选择 c_i 最大的顶点，就是一种贪心的策略，并且我们通过严谨的推导证明了这种贪心是正确的。

好啦，这道题的讲解就到这里啦喵~ 主人学会了吗？下次再遇到类似的题目，也要记得先动动小脑筋，观察和简化条件哦！Mya~

题目大意 ​

题解方法 ​

题解 ​

知识点介绍 ​

题目大意

题解方法

题解

知识点介绍