📝 题目大意

有 $N$ 名程序员，任意两人之间都存在确定的强弱关系且满足传递性。已知 $M$ 条形如"第 $A_i$ 个人比第 $B_i$ 个人强"的信息，判断能否唯一确定最强程序员（即比所有人都强的那位）。若能则输出其编号，否则输出 -1。

💡 解题思路

1. 题目分析：

   • $N \leq 50$，$M \leq \frac{N(N-1)}{2}$，数据范围很小，但题目保证输入信息一定与某种合法的全序关系兼容。
   • 最强程序员的一个关键性质：他不可能在任意一条信息中作为"较弱的一方"出现。换言之，若将每条信息 $A_i \to B_i$ 视为一条有向边（$A_i$ 强于 $B_i$），则最强者的入度必然为 0。

2. 算法推导：

   • 建立入度数组 in_degree，对于每条信息 $(A_i, B_i)$，将 in_degree[B_i] 加 1。
   • 遍历 $1$ 到 $N$，统计入度为 $0$ 的人数 count，并记录对应的候选人编号 candidate。
   • 若 count == 1，则该候选人一定是最强程序员（由题目保证存在合法全序，入度为 0 的唯一人选必然是最强者）；否则无法唯一确定，输出 -1。
   • 为什么不需要 Floyd-Warshall 传递闭包？因为题目只要求识别最强者，而不是计算完整的强弱关系。最强者必然入度为 0，且若有多个入度为 0 的人，则他们之间的强弱关系未知，无法判断谁更强，直接输出 -1 即可。

3. 边界与细节：

   • 当 $M = 0$ 时，所有人入度均为 0，count = N > 1，正确输出 -1。
   • 当存在循环依赖（如 $1 \to 2, 2 \to 1$）时，所有人入度均大于 0，count = 0，输出 -1。但题目保证输入合法，这种情况不会出现。
   • 注意编号从 $1$ 开始，数组大小开到 $N+1$。

⏱️ 复杂度分析

• 时间复杂度：$O(N + M)$，只需统计入度并扫描一遍。
• 空间复杂度：$O(N)$，仅需一个入度数组。

💻 标准代码 (C++)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    // in_degree[i] 表示第 i 个人被多少人"打败"（即作为较弱方出现的次数）
    vector<int> in_degree(N + 1, 0);

    for (int i = 0; i < M; i++) {
        int A, B;
        cin >> A >> B;
        // A 比 B 强，因此 B 的入度 +1
        in_degree[B]++;
    }

    int candidate = -1; // 最强候选人的编号
    int count = 0;      // 入度为 0 的人数

    for (int i = 1; i <= N; i++) {
        if (in_degree[i] == 0) {
            candidate = i;
            count++;
        }
    }

    // 当且仅当恰好有一个人从未被击败时，才能唯一确定最强者
    if (count == 1) {
        cout << candidate << endl;
    } else {
        cout << -1 << endl;
    }

    return 0;
}