[CF1424M] Ancient Language - 拓扑排序

Description

给定一本字典的若干页，每页上会有若干个单词，这本字典的字母顺序是标准顺序的一个排列。求出任意一种排列或者判定非法。

Solution

首先考虑去掉页的限制，对每个单词，定义一个标号 \(iM+j\)，\(i\) 是它的页码，\(j\) 是它是这一页中的第几个，则我们按这个标号对所有单词排序即可

对于相邻的单词，我们找到它们第一个不同的字符（如果有的话），在一张图上对这两个字母之间连边，表示谁在谁的前面

对这张图求拓扑序，拓扑序就是 DFS 的退栈序

可以边求边判，也可以求完以后扫一遍所有边看一下是否非法

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 1005;
const int M = 10005;

map <int,string> mp;
string str[N*N];
int n,k,m;
int g[N][N],exist[N],vis[N],ind[N],fin[N],idx,seq[N],tot;

void dfs(int p)
{
    vis[p]=1;
    // cout<<"dfs "<<p<<endl;
    for(int q=0;q<26;q++)
    {
        if(vis[q] || !exist[q] || g[p][q]==0) continue;
        dfs(q);
    }
    fin[p]=++idx;
    seq[idx]=p;
}

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        int p;
        cin>>p;
        for(int j=1;j<=k;j++)
        {
            string x;
            cin>>x;
            for(char c:x) exist[c-‘a‘]=1;
            mp[p*M+j]=x;
        }
    }
    for(auto i:mp)
    {
        ++m;
        str[m]=i.second;
    }
    for(int i=1;i<m;i++)
    {
        string s=str[i],t=str[i+1];
        int flag=1;
        for(int j=0;j<min(s.length(),t.length());j++)
        {
            if(s[j]!=t[j])
            {
                g[s[j]-‘a‘][t[j]-‘a‘]=1;
                // cout<<"link "<<s[j]-‘a‘<<" "<<t[j]-‘a‘<<endl;
                ind[t[j]-‘a‘]++;
                flag=0;
                break;
            }
        }
        if(flag && s.length()>t.length())
        {
            puts("IMPOSSIBLE");
            return 0;
        }
    }
    for(int i=0;i<26;i++)
    {
        if(exist[i] && ind[i]==0 && !vis[i]) dfs(i);
    }
    for(int i=0;i<26;i++) if(exist[i]) ++tot;
    for(int i=0;i<26;i++)
    {
        for(int j=0;j<26;j++)
        {
            if(g[i][j])
            {
                if(fin[i]<=fin[j]) 
                {
                    puts("IMPOSSIBLE");
                    return 0;
                }
            }
        }
    }
    for(int i=tot;i>=1;i--)
    {
        cout<<(char)(seq[i]+‘a‘);
    }
    
    cout<<endl;
    return 0;
}

[CF1424M] Ancient Language - 拓扑排序

原文：https://www.cnblogs.com/mollnn/p/13881373.html