原题链接

题解

1.\(A<B\) \(\to\) 建立一条A向B的边
2.由于数据范围小，所以可以输入一次进行一次拓扑遍历
3.如果存在矛盾，说明存在环
4.对于拓扑排序进行层次标记，如果最大层等于n，代表每个字母层次分明，有先后次序

code

#include<bits/stdc++.h>
using namespace std;
vector<int> G[30];
int in_copy[30]={0};
int in[30]={0};
struct node
{
    int id,layer;
};
int n,m;
int tuopu()
{
    queue<node> q;
    for(int i=0;i<n;i++) if(!in_copy[i]&&G[i].size()) q.push({i,1});

    int maxlayer=0;
    while(q.size())
    {
        int now=q.front().id,layer=q.front().layer;
        q.pop();

        maxlayer=max(maxlayer,layer);
        for(auto next:G[now])
        {
            in_copy[next]--;
            if(!in_copy[next]) q.push({next,layer+1});
        }
    }

    for(int i=0;i<26;i++) if(in_copy[i])return -1;

    //printf("%d  %d\n",maxlayer,n);
    return (maxlayer==n);
}

void print()
{
    queue<int> q;
    for(int i=0;i<26;i++) if(!in[i]&&G[i].size()) q.push(i);

    while(q.size())
    {
        int now=q.front();
        q.pop();
        printf("%c",now+65);
        for(auto next:G[now])
        {
            in[next]--;
            if(!in[next]) q.push(next);
        }
    }
}
int main()
{
    cin>>n>>m;

    int ends=0;
    for(int i=1;i<=m;i++)
    {
        char a,op,b;
        cin>>a>>op>>b;
        if(ends) continue;
        int a1=a-'A',b1=b-'A';
        G[a1].emplace_back(b1);
        in[b1]++;
        for(int i=0;i<26;i++) in_copy[i]=in[i];

        int tag=tuopu();

        if(tag==-1)
        {
            printf("Inconsistency found after %d relations.\n",i);
            ends=1;
        }
        else if(tag==1)
        {
            printf("Sorted sequence determined after %d relations: ",i);
            print();
            puts(".");
            ends=1;
        }
    }

    if(!ends) printf("Sorted sequence cannot be determined.");
    return 0;
}