P3065 [USACO12DEC]First! G

简要题意

给出 \(n\) 个字符串 \(s_i\)。如果我们称 \(s_i\) 是美好的，当且仅当至少有一种方案规定 \(\texttt{a-z}\) 的大小关系，使得 \(s_i\) 字典序最小。输出有多少个字符串是美好的，并输出美好的字符串。

\(1 \leq n \leq 3\times10^4,1 \leq \sum_{i}|s_i| \leq 3 \times 10^5\)，\(s_i\) 中仅包含小写英文字母。

思路

这道题的做法比较经典。

我们将 \(s_i\) 建出 Trie 树，那么如果一个字符串是美好的，我们要让 Trie 树上每一层的其他字符都比这个字符串在这一层的字符小。然后就可以了。

但是会出现我们无法找到这样的方案的情况。有这两种：

• 存在另一个字符串 \(t\) 是这个字符串 \(s\) 的前缀，这样肯定没有方案。因为无论如何都满足 \(t<s\)。
• 出现矛盾。例如，我们在前面认为 \(x<y\)，后面又认为 \(y<x\)。这样就出现了矛盾，无解。

第一种情况判断比较简单。我们给字符串结尾打上标记，遍历时看看有没有标记即可。注意不要把自己的标记算上了。

第二种情况，我们可以连边 \((x,y)\)。然后就是判断一个有向图有没有环，Tarjan 求强连通分量解决即可。

时间复杂度 \(O(|S|+26n)\)。

代码

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

int n;
const int N = 300005;
int trie[N][26],stop[N],tot;

void insert(const string &x){
    int cur=0;
    for(char i : x){
        if(!trie[cur][i-'a']) trie[cur][i-'a']=(++tot);
        cur=trie[cur][i-'a'];
    }
    stop[cur]++;
}

bool g[30][30];
int dfn[30],low[30],dfncnt,ecc;
bool vis[30];
stack<int> sta;

void tarjan(int u){
    dfn[u]=low[u]=(++dfncnt);vis[u]=1;
    sta.push(u);
    for(int v=0;v<26;v++){
        if(!g[u][v]) continue;
        if(!dfn[v]){
            tarjan(v);low[u]=min(low[u],low[v]);
        }
        else if(vis[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        ecc++;
        while(sta.top()!=u){
            vis[sta.top()]=0;sta.pop();
        }
        sta.pop();vis[u]=0;
    }
}

void clear(){
    memset(g,0,sizeof(g));
    memset(vis,0,sizeof(vis));memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));dfncnt=ecc=0;
    while(!sta.empty()) sta.pop();
}

bool solve(const string &x){
    clear();
    int cur=0;
    for(int i=0;i<x.size();i++){
        if(stop[cur]) return false;
        for(int j=0;j<26;j++){
            if(trie[cur][j]&&x[i]!=(j+'a')) g[x[i]-'a'][j]=1;
        }
        cur=trie[cur][x[i]-'a'];
    }
    for(int i=0;i<26;i++){
        if(!dfn[i]) tarjan(i);
    }
    return ecc==26;
}

string s[N];
vector<string> ret;

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];insert(s[i]);
    }
    for(int i=1;i<=n;i++){
        if(solve(s[i])) ret.push_back(s[i]);
    }
    cout<<ret.size()<<'\n';
    for(string s : ret) cout<<s<<'\n';
    return 0;
}