洛谷 P3065 [USACO12DEC] First! G

原题点这里​​​​​​

题目来源于：洛谷

题目本质：字符串，Hash，字典树Trie

题目思路：

因为涉及到字典序的问题，那么应该能想到字典树。很显然字符串s1如果比字符串s2的字典序小的话，只有两种情况，s1是s2的前缀；以及他们有相同的前缀单在相同前缀后面的部分那一部分s1的优先级更大；所以将所以字符串建成一棵字典树，然后再在字典树上遍历每一串字符串，如果有字符串已经是他的前缀，无论怎么改变26个字母的排列也无济于事，否则判断优先级，及上一段所说的情况二；字符串s1 为 mma 字符串s2 为 mmb。现在要使mmb的优先级大于mma的优先级，他们都有相同的mm前缀，那么要使s2的优先级大，就要使b的优先级大，及相同前缀后面部分的优先级大，跟之前所说的一样。使用括朴排序。构造这样的图，此时a，b在拓扑排序后的顺序是在同一层的，所以可以瞎把a，b交换位置都可以，故可以将a，b交换位置使得s2的优先级大于s1；无法构成拓扑序，因为a，b无论怎么交换位置，mmab都在mmba前面。

代码如下：

#include<bits/stdc++.h>
using namespace std;
struct Node {
	int son[27], end;
} N[300010];
vector<int> E[27];
int n, cnt = 1, ind[30010], ans_sum, used[27][27];
string ans[30010], s[30010];
void insert(string s) {
	int now = 1;
	for (int i = 0; i < s.length(); i++) {
		if (!N[now].son[s[i] - 'a']) N[now].son[s[i] - 'a'] = ++cnt;
		now = N[now].son[s[i] - 'a'];
	}
	N[now].end++;
}
int work(string s) {
	int now = 1;
	for (int i = 0; i < s.length(); i++) {
		int t = s[i] - 'a';
		if (N[now].end) return 0;
		for (int j = 0; j < 26; j++) {
			if (N[now].son[j] && t != j) {
				E[t].push_back(j);
				ind[j]++;
			}
		}
		now = N[now].son[t];
	}
	return 1;
}
int check() {
	queue<int> q;
	for (int i = 0; i < 26; i++) if (!ind[i]) q.push(i);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = 0; i < E[u].size(); i++) {
			ind[E[u][i]]--;
			if (!ind[E[u][i]]) q.push(E[u][i]);
		}
	}
	for (int i = 0; i < 26; i++) if (ind[i]) return 0;
	return 1;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		insert(s[i]);//建字典树
	}
	for (int i = 1; i <= n; i++) {
		memset(used, 0, sizeof(used));
		memset(ind, 0, sizeof(ind));
		for (int j = 0; j < 27; j++) E[j].clear();
		if (!work(s[i])) continue; //如果有人是它的前缀返回0，直接不干了，如果没有，顺便建好图，准备接下来拓扑排序
		if (check()) ans[++ans_sum] = s[i]; //如果符合拓扑序 记录答案
	}
	printf("%d\n", ans_sum);
	for (int i = 1; i <= ans_sum; i++) cout << ans[i] << endl;
	return 0;
}

题解参考于：题解 P3065 【[USACO12DEC]第一!First!】 - 洛谷专栏 (luogu.com.cn)