P1347 排序

· · 题解

P1347 排序

题目翻译：

给出m个关系，求是否能找到他们之间的大小关系。根据能，有冲突，不能来分别作答

思路：

我们可以把小的向大的建一条边，则若a能到b，则a比b小，根据这个原理，我们可以进行拓扑排序，来求出所有点的位置，若要分别讨论三种情况，我们可以得到关系

1.能找到关系： 及有拓扑序，但因为关系是确定的，则必须是一条链，不能有分支。因此我们可以定义一个val表示当前点的列数，则每拓扑出一点，就将他的val变为它前面点的val+1，我们只需要判段，最后的val=n 2.有冲突: 及图中有环 (A>B,B>C,C>A) ,拓扑排序判断环的方式，就是判断排序后，所有排序了的点个数等于总点数，因为有环，就排不到，因此就不会遍历到。 3.不能：以上都不满足就是

实现：

因为n \le 26,m \le 600数很小，因此我们可以每加一条边就进行拓扑排序，在根据情况进行判断。

注意：

给拓扑排序赋值入度时要复制一份，否则会把入度减每

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1000;
struct node{
    int u,val;
};
vector<int>e[N];
int n,m;
int vis[N];
int ru[N];
void toposort(int k,int sum){
    int in[N];
    memcpy(in,ru,sizeof(in));
    vector<int>ans;
    int cnt=0,maxn=0;
    queue<node>q;
    for(int i=0;i<26;i++){
        if(in[i]==0 && vis[i]){
            q.push({i,1});
            cnt++;
        }
    }

    while(!q.empty()){
        int u=q.front().u,val=q.front().val;
        q.pop();
        ans.push_back(u);
        for(auto ed:e[u]){
            in[ed]--;
            if(!in[ed]){
                q.push({ed,val+1});
                cnt++;
                maxn=max(maxn,val+1);
            }
        }
    }
    if(maxn==n){
        printf("Sorted sequence determined after %d relations: ",k);
        for(auto i:ans){
            cout<<char(i+'A'); 
        }
        cout<<'.';
        exit(0);
    }
    else if(cnt!=sum){
        printf("Inconsistency found after %d relations.",k);
        exit(0);
    }

}
int main(){
    cin>>n>>m;
    int cnt=0;
    for(int i=1;i<=m;i++){
        char a,op,b;
        cin>>a>>op>>b;
        int u=int(a-'A'),v=int(b-'A');
        e[u].push_back(v);
        ru[v]++;
        if(!vis[u]){
            cnt++;
            vis[u]=1;
        }
        if(!vis[v]){
            cnt++;
            vis[v]=1;
        }
        toposort(i,cnt);
    }
    printf("Sorted sequence cannot be determined.");
}

拓扑排序讲解