题解：P6491 [COCI 2010/2011 #6] ABECEDA

· · 题解

传送门

题目分析

本题很需要留意细节。

题目会给出多个字符串，且按照新的字典序排列，如题目所给所示：

5
ula
uka
klua
kula
al

显然，在第一列由于 u 在 k 前出现，所以 u 的字典序在 k 前。

动机

题目需要求出新字典序，那么，由多个字符串中存在的具有先后且会传递性的关系，我们可以试向建图方向考虑。若要用图的方法去表达并求出这个关系，我们要去联想到拓扑排序。

建边

我们需要通过一些关系，建一条由字典序小的指向字典序大的边，且建议用邻接表，最简便。

分析字典序的性质，我们可以得到一个结论：

aknoip
akioil

上面这连续两个子串中，前两列均相等，当遍历到第三列时不同，可以比较得到字典序关系，那么建边。需要注意的是，如果此处一旦有不同，那么操作后就应该停止遍历，转而遍历下一对子串。

排序

我们主要讨论以下的两种易错情况：

如下样例：

4
cae
cbf
ccf
abc

如图一所示，在图中 a,b,c 三点成环，会存在矛盾关系，因此我们可以从图上很直观的得出结论：成环必矛盾。

那么直接判断在在拓扑排序完后枚举在图中的点的入度即可。

如下样例：

6
ccf
cah
cac
cbe
ag
ac

如图二所示，在 c 处它的前驱有 h 和 g，忽视未在图上的点，那么就会出现 gcab 或 hcab 两种答案，不符合。

我们可以从图中看出它们的入度均为零。不仅是在第一次将起点入队，也有可能在后面的过程中遇到有多个零入度的点，所以需要在每次枚举后继点时，这里我是将其入队后再判断队中元素大小，若队中存在多个点，那么它可能就会是题目中说的多解情况。

这里为什么不直接退出结束呢？那又要回到图一中的无解情况。

是的，在后面的排序中还有可能出现成环的情况。而无解的判断优先级比多解更高。所以判断完元素后不能直接停止，仍应继续排序，防止因为后续有环出现而导致的误判。

梳理到这，如果将图二中删掉使其多解点就一定有确定的字典序吗？并不完全是，要留意未在图中出现的那两个点。它们没有任何依据关系来被排序，所以在读入时，需要累计不同字母的个数，再在拓扑排序的最后比较已排序的字母与所有出现的字母的个数即可。

而剩下的情况就可以直接输出。

代码呈现

#include<bits/stdc++.h>
using namespace std;
int n,rd[200],ans[30],cnt,c_cnt;//cnt字典序中个数/c_cnt出现的个数
vector<int>e[200];//建议用邻接表
bool have[200];//统计字母个数的
string c[120];
void topo(){
    bool cir=0;
    queue<int>q;
    for(int i=int('a');i<=int('z');i++)//可能可以作为起点,入队       
        if(rd[i]==0&&e[i].size()>0){ 
            q.push(i);
            ans[++cnt]=i;
        }
    while(q.size()){//如果入队后中的元素超过1个，那么可能多解，先记录      
        if(q.size()>1)
            cir=1;
        int top=q.front();
        q.pop();
        for(auto nxt:e[top])
            if(--rd[nxt]==0){
                q.push(nxt);
                ans[++cnt]=nxt;
            }
    }
    for(int i=int('a');i<=int('z');i++)//入度未归零，有环       
      if(rd[i]){
            cout<<"！";
            exit(0);
        }
    if(cir){//顺序的冲突优先级高于多解的可能       
        cout<<"?";
        exit(0);
    }//已排序的字母个数少于出现过的字母的个数   
    if(cnt<c_cnt){
        cout<<"?";
        exit(0);
    }
    for(int i=1;i<=cnt;i++) cout<<char(ans[i]);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<=n;i++) 
        for(int j=0;j<c[i].size();j++) 
            if(!have[int(c[i][j])])//累计出现字母个数              
                have[int(c[i][j])]=1,c_cnt++;   
    for(int i=2;i<=n;i++){                      
        for(int j=0;j<min(c[i].size(),c[i-1].size());j++){//每个子串首字母，互异则前者字典序更小           
            if(j==0&&c[i-1][0]!=c[i][0]){       
                int x=int(c[i-1][0]),y=int(c[i][0]);
                e[x].push_back(y);
                rd[y]++;
                break;
            }//各自前一个字符相同，则后一个可以比较大小 
            if(j!=0&&c[i-1][j-1]!=c[i][j-1]) 
                break;//某两行相比较，如果一旦其中某一列不同，那么即使后面相同，也不能进行关系比较 
            if(j!=0&&c[i-1][j]!=c[i][j]){
                int x=int(c[i-1][j]),y=int(c[i][j]);
                e[x].push_back(y);
                rd[y]++;
                break;                          
            }
        }
    }
    topo();
    return 0;
}