拓朴排序例题

1.拓扑排序可以用来判断图中是否有环，

2.还可以用来判断图是否是一条链。

 复制Markdown  展开

题目描述

一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列，例如，一个有序的数列 A,B,C,DA,B,C,D 表示A<B,B<C,C<DA<B,B<C,C<D。在这道题中，我们将给你一系列形如 A<BA<B 的关系，并要求你判断是否能够根据这些关系确定这个数列的顺序。

输入格式

第一行有两个正整数 n,mn,m，nn 表示需要排序的元素数量，2\leq n\leq 262≤n≤26，第 11 到 nn 个元素将用大写的 A,B,C,D\dotsA,B,C,D… 表示。mm 表示将给出的形如 A<BA<B 的关系的数量。

接下来有 mm 行，每行有 33 个字符，分别为一个大写字母，一个 < 符号，一个大写字母，表示两个元素之间的关系。

输出格式

若根据前 xx 个关系即可确定这 nn 个元素的顺序 yyy..y（如 ABC），输出

Sorted sequence determined after xxx relations: yyy...y.

若根据前 xx 个关系即发现存在矛盾（如 A<B,B<C,C<AA<B,B<C,C<A），输出

Inconsistency found after x relations.

若根据这 mm 个关系无法确定这 nn 个元素的顺序，输出

Sorted sequence cannot be determined.

（提示：确定 nn 个元素的顺序后即可结束程序，可以不用考虑确定顺序之后出现矛盾的情况）

输入输出样例

输入 #1复制

4 6
A<B
A<C
B<C
C<D
B<D
A<B

输出 #1复制

Sorted sequence determined after 4 relations: ABCD.

输入 #2复制

3 2
A<B
B<A

输出 #2复制

Inconsistency found after 2 relations.

输入 #3复制

26 1
A<Z

输出 #3复制

Sorted sequence cannot be determined.

说明/提示

2 \leq n \leq 26,1 \leq m \leq 6002≤n≤26,1≤m≤600。

这一道题一看就知道是拓扑排序。

1.首先观察数据范围和输出，数据范围26，是真的小，就说明多搞一搞肯定也T不了。输出要求输出到第几次就行了，或者不行了，就说明我们每建一条边就需要一次拓扑排序。

2.再看这道题的三种情况。第一个是有稳定顺序，第二个是有环，第三个是无环但是也没有稳定拓扑顺序。然后我们对这三个问题进行依次解决。

第一个问题：有稳定拓扑排序说明拓扑排序的层数是n。也就是下面代码的val。一层一层下去如果是n层的话，那么这个图里面肯定包含一个n长度的链，我们只要看最大的层数是不是n就可以了，也就是代码的ans==n。

第二个问题就是成环，拓扑排序判断有没有环其实很简单，如果拓扑排序没能遍历所有的点，就说明存在一个环。也就是下面的sum==s1.size()。s1是用来存储目前元素（点）个数的。

最后一种情况最简单，如果前两种都不是，那肯定就是最后一种了！

#include <bits/stdc++.h>
typedef long long ll;
typedef double db;
#define MAXN 50
using namespace std;
int n,m;
struct Node{
    int u;
    int val;
    Node(int u=0,int val=0):u(u),val(val){}
};
vector<int> vec[MAXN];
int ru[MAXN];
int sum;
int ans;
int k;
set<int> s1;
void make(){
    queue<int> q;
    int ru1[MAXN];
    memset(ru1,0,sizeof(ru1));
    for(int i=0; i<26; i++){
        for(int j=0; j<vec[i].size(); j++){
            ru1[vec[i][j]]++;
        }
    }
    for(int i=0; i<26; i++){
        if(ru1[i]==0&&s1.count(i)){
            q.push(i);
            cout<<char(i+'A');
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0; i<vec[u].size(); i++){
            int v=vec[u][i];
            ru1[v]--;
            if(ru1[v]==0){
                q.push(v);
                cout<<char(v+'A');
            }
        }
    }
}
int have;
void topo(){
    queue<Node> q;
    for(int i=0; i<26; i++){
        if(ru[i]==0&&s1.count(i)){
            q.push(Node(i,1));
            sum++;
        }
    }
    while(!q.empty()){
        int u=q.front().u;
        int val=q.front().val;
        q.pop();
        for(int i=0; i<vec[u].size(); i++){
            int v=vec[u][i];
            ru[v]--;
            if(ru[v]==0){
                sum++;
                q.push(Node(v,val+1));
                ans=max(ans,val+1);
            }
        }
    }
    if(ans==n){
        printf("Sorted sequence determined after %d relations: ",k);
        make();
        cout<<".";
        exit(0);
    }
    if(sum!=have){
        printf("Inconsistency found after %d relations.",k);
        exit(0);
    }
}
int ru2[MAXN];
int main(){
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        string s;
        cin>>s;
        k=i;
        vec[s[0]-'A'].push_back(s[2]-'A');
        s1.insert(s[0]-'A');
        s1.insert(s[2]-'A');
        have=s1.size();
        ru2[s[2]-'A']++;
        sum=0;
        ans=0;
        memcpy(ru,ru2,sizeof(ru2));
        topo();
    }
    printf("Sorted sequence cannot be determined.");
    return 0;
}