假的字符串 Trie+拓扑排序

假的字符串 Trie+拓扑排序

题目链接

题意：

给定n个字符串，互不相等，你可以任意指定字符之间的大小关系（即重定义字典序），求有多少个串可能成为字典序最小的串，并输出它们。

思路：

我们可以对每个字符串单独判断，考虑当前 \(s_i\) 为字典序最小的串。那么首先要满足的条件就是 \(s_i\) 的前缀不能出现在字典中，前缀的字典序一定比 \(s_i\) 小。接着我们考虑其他字符串怎么判断？不妨将所有串插入到Trie中，那么我们可以遍历 \(s_i\) 的每个节点，如果当前节点有其他子节点，那么说明 \(s_i\) 的下一个字母的字典序一定小于其余字母。因此，我们就会得到很多对偏序关系。只要偏序关系不出现矛盾，那么就一定可以构造出新的字符大小关系来保证 \(s_i\) 是字典中字典序最小的串。那么我们可以对这些偏序关系建图，然后拓扑排序判断是否有环即可。

代码：

#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;

typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 3e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 0;

//Trie
struct Trie{
   int ch[N][26];
   int cnt[N];
   int idx=0;
   void insert(string s){
      int p=0;
      for(auto c:s){
         int j=c-'a';
         if(!ch[p][j]) ch[p][j]=++idx;
         p=ch[p][j];
      }
      cnt[p]++;
   }
   int query(string s){
      int p=0;
      for(auto c:s){
         int j=c-'a';
         if(!ch[p][j]) return 0;
         p=ch[p][j];
      }
      return cnt[p];
   }
}trie;

void Showball(){
   int n;
   cin>>n;
   vector<string> a(n);
   for(int i=0;i<n;i++){
      cin>>a[i];
      trie.insert(a[i]);
   }
   
   auto check=[&](string s){
      vector<int> e[26];
      vector<int> d(26,0);
      int p=0;
      for(auto c:s){
         int j=c-'a';
         for(int i=0;i<26;i++){
            if(trie.ch[p][i]){
               if(i==j) continue;
               e[j].pb(i);
               d[i]++;
            }
         }
         if(trie.cnt[p]) return false;
         p=trie.ch[p][j];
      }
      //topo判断环
      int cnt=0;
      queue<int> q;
      for(int i=0;i<26;i++) if(!d[i]) q.push(i);
      while(!q.empty()){
         int u=q.front();q.pop();
         cnt++;
         for(auto v:e[u]){
            if(!--d[v]) q.push(v);
         }
      }
      return cnt==26;
   };

   vector<string> ans;
   for(auto s:a){
      if(check(s)) ans.pb(s);
   }
   cout<<ans.size()<<endl;
   for(auto s:ans) cout<<s<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    if(cases) cin>>T;
    while(T--)
    Showball();
    return 0;
}