牛客练习赛11 假的字符串 （Trie树+拓扑找环）
链接：https://ac.nowcoder.com/acm/problem/15049
来源：牛客网
给定n个字符串，互不相等，你可以任意指定字符之间的大小关系（即重定义字典序），求有多少个串可能成为字典序最小的串，并输出它们
题解：对于第i个字符串来说，如果有一个串是他的前缀，那么这个前缀的字典序重定义后是肯定比他小的，所以我们用trie树保存前缀
对于当前字符串，从该字符串的第i个字母向其父亲节点上的其他字母连边，表示存在大小关系\(str[i]>str[others]\) 这样就指定了 第i个字母的与其他字母的大小关系了，如果当前关系成立的话，就不会出现a>b>a这样的情况 即不会出现环的情况，所以我们用拓扑排序判断是否有环即可
/**
* ┏┓ ┏┓
* ┏┛┗━━━━━━━┛┗━━━┓
* ┃ ┃
* ┃ ━ ┃
* ┃ ＞ ＜ ┃
* ┃ ┃
* ┃... ⌒ ... ┃
* ┃ ┃
* ┗━┓ ┏━┛
* ┃ ┃ Code is far away from bug with the animal protecting
* ┃ ┃ 神兽保佑,代码无bug
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┗━━━┓
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛
*/
// warm heart, wagging tail,and a smile just for you!
//
// _ooOoo_
// o8888888o
// 88" . "88
// (| -_- |)
// O\ = /O
// ____/`---'\____
// .' \| |// `.
// / \||| : |||// \
// / _||||| -:- |||||- \
// | | \ - /// | |
// | \_| ''\---/'' | |
// \ .-\__ `-` ___/-. /
// ___`. .' /--.--\ `. . __
// ."" '< `.___\_<|>_/___.' >'"".
// | | : `- \`.;`\ _ /`;.`/ - ` : | |
// \ \ `-. \_ __\ /__ _/ .-` / /
// ======`-.____`-.___\_____/___.-`____.-'======
// `=---='
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// 佛祖保佑 永无BUG
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef unsigned long long uLL;
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define bug printf("*********\n")
#define FIN freopen("input.txt","r",stdin);
#define FON freopen("output.txt","w+",stdout);
#define IO ios::sync_with_stdio(false),cin.tie(0)
#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"
#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"
#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"
const int maxn = 2e5 + 5 + 3e4;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double Pi = acos(-1);
LL gcd(LL a, LL b) {
return b ? gcd(b, a % b) : a;
}
LL lcm(LL a, LL b) {
return a / gcd(a, b) * b;
}
double dpow(double a, LL b) {
double ans = 1.0;
while(b) {
if(b % 2)ans = ans * a;
a = a * a;
b /= 2;
} return ans;
}
LL quick_pow(LL x, LL y) {
LL ans = 1;
while(y) {
if(y & 1) {
ans = ans * x % mod;
} x = x * x % mod;
y >>= 1;
} return ans;
}
int du[27];
int mp[27][27];
int tuop() {
queue<int> qu;
while(!qu.empty()) qu.pop();
memset(du, 0, sizeof(du));
for(int i = 0; i < 26; ++i) {
for(int j = 0; j < 26; ++j) {
if(mp[i][j] == 1) du[j]++;
}
}
for(int i = 0; i < 26; ++i) {
if(du[i] == 0) qu.push(i);
}
int num = 0;
while(!qu.empty()) {
int u = qu.front();
qu.pop();
num++;
for(int i = 0; i < 26; ++i) {
if(mp[u][i] == 1) {
du[i]--;
if(du[i] == 0) qu.push(i);
}
}
}
return num;
}
const int maxChild = 26;
const int maxNode = maxn;
int tot = 0;
int child[maxNode | 10][maxChild];
//int cnt; //该结点后缀的数量
int isWord[maxNode];
void insert(string s) {
int pos, cur = 0;
for (int i = 0; i < s.length(); ++i) {
pos = s[i] - 'a';
if (child[cur][pos] == 0)
child[cur][pos] = ++tot;
cur = child[cur][pos];
//cnt++[cur];
}
isWord[cur] = 1;
}
int query(string s) {
int pos, cur = 0;
memset(mp, 0, sizeof(mp));
for (int i = 0; i < s.length(); ++i) {
pos = s[i] - 'a';
for(int j = 0; j < maxChild; ++j) {
if(pos == j) continue;
if(child[cur][j] != 0)
mp[pos][j] = 1;
}
if (child[cur][pos] == 0)
return 0;
if(isWord[cur])
return 0;
cur = child[cur][pos];
}
return tuop() == 26;
}
string str[maxn];
int flag[maxn];
int main() {
#ifndef ONLINE_JUDGE
FIN
#endif
IO;
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> str[i];
insert(str[i]);
}
int ans = 0;
for(int i = 1; i <= n; i++) {
if(query(str[i])) {
flag[i] = 1;
ans++;
}
}
// printf("%d\n", ans);
cout << ans << '\n';
for(int i = 1; i <= n; i++) {
if(flag[i]) {
cout << str[i] << '\n';
}
}
return 0;
}
