拓扑排序 yyds

从头迭代到尾，运用拓扑排序的性质解题就行，思路贼好想

难点在如何建图：

1. 首先问如何记录迭代次数？
   · 边输入边拓扑就行，具体看代码，时间复杂度也不大
2. 如果输入A<B,B<C那么怎么建？
   · 开个st数组，如果前面加过后就不用再加了，证明很简单

上代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int N = 26;

int n, m, cnt, kind, d[N], in[N];
bool st[N];

void top_sort(int x, vector<int> g[])
{
    queue<int> q;
    string res;
    bool flag = true;
    memcpy(d, in, sizeof in);

    for(int i = 0; i < n; i++)
        if(d[i] == 0) q.push(i);


    while(q.size())
    {
        if(q.size() > 1)  flag = false; 
        // 如果队列里元素数大于1，以C这个点为例，那么就说明能到C的点数大于一，就出现了矛盾
        int t = q.front();
        q.pop();

        res += 'A' + t;
        vector<int>::iterator it = g[t].begin();
        for(; it != g[t].end(); it++)
        {
            if( --d[*it] == 0) q.push(*it);
        }
    }

    if(res.length() == n && flag)
    {
        kind = 1;
        cout << "Sorted sequence determined after " << x << " relations: " << res << ".\n";
    }
    if(res.length() < cnt)
    {
        kind = 2;
        printf("Inconsistency found after %d relations.\n", x);
    }

}

int main()
{
    while(scanf("%d %d", &n, &m), n || m)
    {

        memset(in, 0, sizeof in);
        memset(st, 0, sizeof st);
        cnt = kind = 0;
        vector<int> g[N];

        for(int i = 1; i <= m; i++)
        {
            string str;
            cin >> str;
            if (kind)   continue;

            int a = str[0] - 'A', b = str[2] - 'A';

            // st[]保证了不重复建边
            if(!st[a])
            {
                st[a] = true;
                cnt ++;
            }

            if(!st[b])
            {
                st[b] = true;
                cnt ++;
            }
            in[b]++;
            g[a].push_back(b);
            top_sort(i, g);
        }
        if(!kind)
        {
            puts("Sorted sequence cannot be determined.");
        }
    }
    return 0;
}