CF510C Fox And Names 题解

题意

求一种满足让 \(n\) 个字符串按大小排列的字典序。

分析

首先根据输入的字符串建图：对于每一个字符串 \(s_i\) ，枚举所有在它之前的字符串 \(s_j\)，刨去两个字符串相同的前缀后建立一条由 \(s_i\) 第一个字符指向 \(s_j\) 第一个字符的有向边。然后跑一遍拓扑，如果跑出来 topo 数组的大小正好是 \(26\)，说明有一条路径，否则无解。注意特判一个字符串是另一个字符串前缀的情况。

代码

#include 
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline void qread(){}template
inline void qread(T1 &a,T2&... b)
{
    register T1 x=0;register bool f=false;char ch=getchar();
    while(ch<'0') f|=(ch=='-'),ch=getchar();
    while(ch>='0') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    x=(f?-x:x);a=x;qread(b...);
}
templateinline T1 qmax(const T1 &x,const T2 &y){return x>y?x:y;}
templateinline T1 qmin(const T1 &x,const T2 &y){return xedge;
void add_edge(int u,int v){edge.push_back(Edge(v,head[u]));head[u]=edge.size()-1;}
vectortopo;
void topo_sort()
{
    topo.clear();queueq;int i;
    for(i=0;i<26;i++) if(!in[i]) q.push(i);
    while(!q.empty())
    {
        int u=q.front();q.pop();topo.push_back(u);
        for(i=head[u];i!=-1;i=edge[i].nxt) if(!(--in[edge[i].to])) q.push(edge[i].to);
    }
}
int main()
{
    qread(n);int i,j;mem(head,-1);bool flag=true;
    for(i=0;istrlen(s[i]))
            {
                bool f=true;
                for(int k=0;k