题目描述
给定n个字符串，互不相等，你可以任意指定字符之间的大小关系（即重定义字典序），求有多少个串可能成为字典序最小的串，并输出它们
输入描述:
第一行一个数表示n
之后n行每行一个字符串表示给定的字符串
输出描述:
第一行输出一个数x表示可行的字符串个数
之后输出x行，每行输出一个可行的字符串
输出的顺序和输入的顺序一致
示例1
输入
6 mcfx ak ioi wen l a
输出
5 mcfx ioi wen l a
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef struct node{
string s;int biao;
friend bool operator <(node aa,node bb){
return aa.s.length()<bb.s.length();
}
}node;
string str[30005];
node dd[30005];
int cnt,root;
typedef struct nop{
int a[26],ans;
}nop;
nop d[300005];
bool vvis[30005];
int newnode(){
cnt++;d[cnt].ans=0;
for(int i=0;i<26;i++) d[cnt].a[i]=0;
return cnt;
}
void inset(string s,int tt){
int len=s.length();int temp=root;
for(int i=0;i<len;i++){
int t=s[i]-'a';
if(d[temp].a[t]==0){
d[temp].a[t]=newnode();
}
temp=d[temp].a[t];
if(d[temp].ans!=0){
vvis[tt]=1;return ;
}
if(i==len-1){
d[temp].ans=tt;
}
}
return ;
}
vector<int>v_[26];
int dis[26];queue<int>que;
bool check(){
memset(dis,0,sizeof(dis));
for(int i=0;i<26;i++){
for(int j=0;j<v_[i].size();j++){
dis[v_[i][j]]++;
}
}
while(!que.empty()) que.pop();
for(int i=0;i<26;i++){
if(!dis[i]) que.push(i);
}
if(que.empty()) return 0;
while(!que.empty()){
int t=que.front();que.pop();
for(int i=0;i<v_[t].size();i++){
dis[v_[t][i]]--;
if(dis[v_[t][i]]==0) que.push(v_[t][i]);
}
}
for(int i=0;i<26;i++){
if(dis[i]!=0) return 0;
}
return 1;
}
int main(){
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>str[i];
dd[i].s=str[i];dd[i].biao=i;
}
sort(dd+1,dd+n+1);
root=newnode();
for(int i=1;i<=n;i++){
inset(dd[i].s,dd[i].biao);
}
for(int i=1;i<=n;i++){
if(vvis[i]) continue;
int len=str[i].length();
int temp=root;
for(int j=0;j<len;j++){
int t=str[i][j]-'a';
for(int k=0;k<26;k++){
if(d[temp].a[k]!=0&&k!=t){
v_[t].push_back(k);
}
}
temp=d[temp].a[t];
}
if(!check()) vvis[i]=1;
for(int j=0;j<26;j++) v_[j].clear();
}
int cnt=0;
for(int i=1;i<=n;i++){
if(vvis[i]==1) continue;
cnt++;
}
cout<<cnt<<endl;
for(int i=1;i<=n;i++){
if(vvis[i]==1) continue;
cout<<str[i]<<endl;
}
return 0;
}