image.png

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

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
using namespace std;
//int a[100],b[100];
//set<int>Next[30];//前提是一个点到另一个点的之间有一条，但是这题会出现重复的现象
vector<int>Next[300]; 
//vector<int>peop;//枚举People需要字典序排列，vector改成set
set<int> peop;
int In[300],have[300],vis[300],res[300],num;//num record the numbers of people 
/*
void qsort(int L,int R)
{
    int i=L,j=R,mid;
    while(i<=j)
    {
        int mid=a[(i+j)/2];
        while(a[i]<mid) i++;
        while(a[j]>mid) j--;
        if(i<=j)
        {
            swap(a[i],a[j]);
            swap(b[i],b[j]);
            i++,j--;
        } 
    }
    if(L<j) qsort(L,j);
    if(i<R) qsort(i,R);
}
*/
int main(void)
{
    //freopen("D:\\input10.txt","r",stdin);
    char res[110];
    int count=0;
    while(cin.getline(res,100))
    {
        //cout<<res<<endl;
        
        int p1=res[0]-'A';
        int p2=res[2]-'A';
        count++;
        //a[count]=p1;
        //b[count]=p2;
        //cout<<"p1="<<p1<<" p2="<<p2<<endl;
        if(have[p1]==false)
        {
            have[p1]=true;
            peop.insert(p1); 
            num++;
        }
        if(have[p2]==false)
        {
            have[p2]=true;
            peop.insert(p2);
            num++;
        }
        //Next[p1].insert(p2);
        Next[p1].push_back(p2);
        In[p2]++;
    }
    /*
    qsort(1,count);
    for(int i=1;i<=count;i++) 
    {
        printf("%c %c\n",a[i]+'A',b[i]+'A'); 
    } 
    for(int i=0;i<26;i++) cout<<have[i];
    cout<<endl; 
    */
    int cnt=0,ans[100];//record the people who mean 
    queue<int>q;
    for(set<int>::iterator it=peop.begin();it!=peop.end();it++)
    {
        int p = *it;
        if(In[p]==0)
        {
            vis[p]=true;
            q.push(p);
        }
    }
    //cout<<"num="<<num<<endl;
    while(!q.empty())
    {
        int p = q.front(); q.pop();
        //cout << (char)('A'+p)<<endl;
        ans[++cnt]=p;
        if(cnt==num)
        {
            for(int i=1;i<=num;i++) cout<<(char)('A'+ans[i]);
        }
        for(int i=0;i<Next[p].size();i++)
        {
            //后继节点入度减一 
            int u = Next[p][i];
            In[u]--;
        }
        for(set<int>::iterator it=peop.begin();it!=peop.end();it++)
        {
            int x = *it;
            //cout<<In[x]<<" ";
            if(In[x]==0 && vis[x]==false)
            {
                vis[x]=true;
                q.push(x);
            }
        }
        //cout<<endl;
    }
    if(cnt!=num) cout<<"No Answer!";
    return 0;
}