信息奥赛题解｜产生冠军

---

🚀 题目浏览

【题目描述】

有一群人，打乒乓球比赛，两两捉对撕杀，每两个人之间最多打一场比赛。

球赛的规则如下：

• 如果 A 打败了 B，B 又打败了 C，而 A 与 C 之间没有进行过比赛，那么就认定，A 一定能打败 C。
• 如果 A 打败了 B，B 又打败了 C，而且 C 又打败了 A，那么 A、B、C 三者都不可能成为冠军。

根据这个规则，无需循环较量，或许就能确定冠军。你的任务就是面对一群比赛选手，在经过了若干场撕杀之后，确定是否已经实际上产生了冠军。

【输入】

多组数据，请处理到 $n=0$ 为止。

每组数据以一个整数 $n\ (n\lt 1000)$ 开头，后跟 $n$ 对选手的比赛结果，比赛结果以一对选手名字（中间隔一空格）表示前者战胜后者。

【输出】

对于每组数据，若你判断出产生了冠军，则在一行中输出 Yes，否则在一行中输出 No。

【输入样例】

3
Alice Bob
Smith John
Alice Smith
5
a c
c d
d e
b e
a d
0

【输出样例】

Yes
No

【题目来源】

https://vjudge.net/problem/HDU-2094

---

☘️ 题解分析

思维题。

结合 STL 中的 set 使用，效果巨佳。

---

🧑🏻‍💻 C++ 代码

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
int n;

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    string win, lose;
    while (cin >> n && n) {
        // 设定两个集合，存储胜者和败者
        set<string> winners, losers;

        // 根据n轮结果，往集合中加入玩家
        for (int i = 1; i <= n; i++) {
            cin >> win >> lose;
            // 当前赢家未出现在败者名单中，将其加入胜者名单
            if (losers.find(win) == losers.end()) winners.insert(win);
            // 当前败者出现在胜者名单中，将其从胜者名单中抹去
            if (winners.find(lose) != winners.end()) winners.erase(lose);
            losers.insert(lose);
        }
        // 判断是否有胜者
        if (winners.size() == 1) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;
}