排序

洛谷P1347 排序

题目争议

讲真，我认为题面是有一点问题的：

题目中有这样一些语句“若根据前x个关系即发现存在矛盾（如A<B,B<C,C<A），输出：Inconsistency found after 2 relations.” 和 “提示：确定n个元素的顺序后即可结束程序，可以不用考虑确定顺序之后出现矛盾的情况”

首先，那个输出应该是“Inconsistency found after x relations.”

其次，已知(A<B,B<C)，根据那个提示我们可以直接判断(A<B<C)然后后面的(C<A)则可以不用管了，但是题目解释的却是不合法

以上是我的想法，我在编程中按照提示编的（AC了），所以题意争议大概不影响做题？（大雾...）

解题算法

好了，废话不多说，这道题我会用两种做法完成：拓扑排序、变种Floyd

拓扑排序

再一次无耻地宣传 一波我的关于拓扑排序的学习记录

• 怎么想到拓扑排序的？

因为题目中的规则就是元素之间的顺序并且是有向图（还是无并列关系的顺序），所以可以使用拓扑排序

• 怎么拓扑排序？

因为要求输出第(i)步要么完成排序要么形成环，所以每输入一组大小关系就要进行一次拓扑排序

这题之所以是蓝题，大概就是因为每次拓扑排序需要处理三种情况：

1. 形成合法拓扑序列

2. 形成非法的环

3. 暂时没有形成完整的拓扑序列但也不是环

（注意拓扑排序不处理题目中的第三种情况，即无法确定的情况）

• 分类讨论

题目中的第三种情况是最简单的：当输入完成后还没有输出则说明无法确定出拓扑序列

下面重点讲拓扑排序中的三种情况

1. 判断当前形成环的条件：

①输入的两个元素(u)、(v)相同（自环）

②答案数组的长度(<)目前所出现过的元素个数（下面会给出说明）

2. 判断当前已经形成合法拓扑序列的条件：

①不满足以上形成环的条件

②答案数组的长度(==N)（标准的拓扑排序合法判断）

3. 暂时没有形成合法序列但也不形成环（下面会给出说明）：

①在最开始入队时，同时存在多个入度为0的点

②在循环队列处理中，有超过1个的点在同一轮入队

• 判断说明

1. 答案数组的长度(<)目前所出现过的元素个数（形成环），如图：
   

2. 在最开始入队时，同时存在多个入度为0的点（暂时不形成）

因为题目已经说明拓扑序列没有并列关系，所以这题一个合法的序列不可能同时存在两个源点（即入度为0的点）

3. 在循环队列处理中，有超过1个的点在同一轮入队（暂时不形成）

同上，因为没有并列关系，所以一个点的后继应该只有一个而不是多个，那么一次只能入队一个，如果一次入队多个则说明当前还不形成合法序列

• 代码Code

注释版配合上面的讲解，敲详细呀qwq~

#include <bits/stdc++.h>
using namespace std;
queue<int> q;
char a,b,op;
vector<int> ans;
int n,m,tot,sum,in[1001],inn[1001],head[1001],flag[1001];

struct node {
    int to,net;
} e[1001];

inline void add(int u,int v) {
    e[++tot].to=v;
    e[tot].net=head[u];
    head[u]=tot;
}

inline int check() {  //拓扑排序 
    ans.clear();  //一定要清空 
    int k=0,kk=0;
    for(register int i=1;i<=n;i++) {
        inn[i]=in[i];  //因为队列处理会影响in[]，所以要赋值 
        if(in[i]==0&&flag[i]==1) {
            if(k==0) k=1;
            else kk=1;  //如果kk=1，则说明同时存在多个入度为0的点 
            q.push(i);
        }
    }
    if(q.empty()) return 1;  //队列为空，说明是环 
    while(!q.empty()) {
        int k=0,now=q.front();  //这里k要重新赋为0 
        q.pop();
        ans.push_back(now);  //存入答案数组 
        for(register int i=head[now];i;i=e[i].net) {
            int v=e[i].to;
            if(--inn[v]==0) {
                if(k==0) k=1;
                else kk=1;  //如果kk=1，则说明一次入队多个点 
                q.push(v);
            }
        }
    }
    if(ans.size()<sum) return 1;  //答案数组的长度<目前出现过的所有元素，形成环 
    if(kk==1) return 2;
    return 0;
}

int main() {
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=m;i++) {
        cin>>a>>op>>b;
        if(a==b) {  //自环的情况 
            printf("Inconsistency found after %d relations.",i);
            return 0;
        }
        add(a-'A'+1,b-'A'+1);  //连边 
        in[b-'A'+1]++;  //后者的入度++ 
        if(flag[a-'A'+1]==0) sum++;  //统计当前出现过的不重复的元素个数 
        if(flag[b-'A'+1]==0) sum++;
        flag[a-'A'+1]=flag[b-'A'+1]=1;
        int x=check();
        if(x==1) {  //环的情况 
            printf("Inconsistency found after %d relations.",i);
            return 0;
        } 
        if(ans.size()==n&&x==0) {  //形成了合法的拓扑序列 
            printf("Sorted sequence determined after %d relations: ",i);
            for(register int i=0;i<ans.size();i++) cout<<char(ans[i]+'A'-1);
            printf(".");
            return 0;
        }
    }
    printf("Sorted sequence cannot be determined.");  //最终的无解情况 
    return 0;
}

变种Floyd

因为我本人是用的是拓扑排序，而变种Floyd是右边dalao做出来的，所以这里直接挂出dalao的题解