蓝桥杯 ADV-169 算法提高士兵排队问题

试题
有Ｎ个士兵(1≤Ｎ≤26)，编号依次为Ａ,Ｂ,Ｃ,…，队列训练时，指挥官要把一些士兵从高到矮一次排成一行，但现在指挥官不能直接获得每个人的身高信息，只能获得“P1比P2高”这样的比较结果(P1、P2∈Ａ,Ｂ,Ｃ,…,Ｚ,记为 P1>P2)，如”Ａ>Ｂ”表示Ａ比Ｂ高。
请编一程序，根据所得到的比较结果求出一种符合条件的排队方案。
（注：比较结果中没有涉及的士兵不参加排队）
输入要求
比较结果从文本文件中读入（文件由键盘输入），每个比较结果在文本文件中占一行。
输出要求
若输入数据无解，打印“No Answer!”信息，否则从高到矮一次输出每一个士兵的编号，中间无分割符，并把结果写入文本文件中，文件由键盘输入：
样例输入
A>B
B>D
F>D
样例输出
AFBD

分析：高>矮，记作矮入度+1。每次找到没有排过队并且入度为0的士兵，拉出来排队，然后把紧跟后面的士兵的入度-1，一直这样循环。当找不到没排队且入度为0的士兵，判断：如果士兵全部排好了，正常输出；否则出现了环，无法确定顺序，输出No Answer!

#include <iostream>
#include <cstring>
#include <vector>
#include <set>
using namespace std;
int main() {
    int in[151], vis[150] = {0};
    set<int> se;
    vector<int> a[150];
    memset(in, -1, sizeof(in));
    string s, ans;
    while (cin >> s) {
        if (in[s[0]] == -1) in[s[0]] = 0;
        if (in[s[2]] == -1) in[s[2]] = 0;
        in[s[2]]++;
        a[s[0]].push_back(s[2]);
        se.insert(s[0]);
        se.insert(s[2]);
    }
    while (1) {
        int cnt = 0, begin;
        for (int i = 1; i <= 150; i++) {
            if (in[i] == 0 && vis[i] == 0) {
                begin = i;
                cnt++;
            }
        }
        if (cnt == 0) {
            if (ans.length() == se.size()) {
                cout << ans;
            } else
                cout << "No Answer!";
            break;

        } else {
            ans += (char) begin;
            vis[begin] = 1;
            for (int i = 0; i < a[begin].size(); i++)
                in[a[begin][i]]--;
        }
    }
    return 0;
}

#include <iostream>

#include <cstring>

#include <vector>

#include <set>

using namespace std;

int main() {

int in[151], vis[150] = {0};

set<int> se;

vector<int> a[150];

memset(in, -1, sizeof(in));

string s, ans;

while (cin >> s) {

if (in[s[0]] == -1) in[s[0]] = 0;

if (in[s[2]] == -1) in[s[2]] = 0;

in[s[2]]++;

a[s[0]].push_back(s[2]);

se.insert(s[0]);

se.insert(s[2]);

}

while (1) {

int cnt = 0, begin;

for (int i = 1; i <= 150; i++) {

if (in[i] == 0 && vis[i] == 0) {

begin = i;

cnt++;

}

if (cnt == 0) {

if (ans.length() == se.size()) {

cout << ans;

} else

cout << "No Answer!";

break;

} else {

ans += (char) begin;

vis[begin] = 1;

for (int i = 0; i < a[begin].size(); i++)

in[a[begin][i]]--;

}

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版