P3065 [USACO12DEC] First! G

点击查看代码

#include<bits/stdc++.h>
using namespace std;const int N=3e5+10;
string s[N];
int tr[N][26],idx,ed[N];
int ind[26];
bool g[26][26];
int n;void insert(string s)
{int p=0;for(const char& c : s){int u=c-'a';if(!tr[p][u]) tr[p][u]=++idx;p=tr[p][u];}ed[p]=1;
}bool check(string s)
{memset(g,0,sizeof g);memset(ind,0,sizeof ind);int p=0;for(const char& c : s){if(ed[p]==1) return false;int u=c-'a';for(int v=0;v<26;v++){if(v!=u&&tr[p][v]){if(!g[u][v]){g[u][v]=1;ind[v]++;}}}p=tr[p][u];}queue<int> q;for(int i=0;i<26;i++){if(ind[i]==0){q.push(i);}}int cnt=0;while(!q.empty()){int u=q.front();q.pop();cnt++;for(int v=0;v<26;v++){if(g[u][v]){if(--ind[v]==0){q.push(v);}}}}return cnt==26;
}int main()
{ios::sync_with_stdio(0),cin.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>s[i];insert(s[i]);}vector<string> ans;for(int i=1;i<=n;i++){if(check(s[i])){ans.push_back(s[i]);}}cout<<ans.size()<<"\n";for(const string& res : ans){cout<<res<<"\n";}return 0;}