牛客练习赛11 B (字典树+拓扑排序）

题意

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

做法

每一个串如果有一个串是它的前缀，则肯定不行
否则每次从这个字母向同一个父亲的其他字母连边
可以通过拓扑排序找环

这题空间很紧啊 服了

#include 
using namespace  std;
//#define  int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define pb  push_back
#define inf 1<<62
#define endl "\n"
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define de_bug(x) cerr << #x << "=" << x << endl
#define all(a) a.begin(),a.end()
#define IOS   std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  fer(i,a,b)  for(int i=a;i<=b;i++)
#define  der(i,a,b)  for(int i=a;i>=b;i--)
const int mod = 1e9 + 7;
const int N = 3e5 + 10;
int n, m , k;
vi g[33];
int d[33];
int son[N][26];
int idx;
int cnt[N];
void insert(string s) {
	int p = 0;
	for(int i = 0; i < (int)s.size(); i++) {
		int u = s[i] - 'a';
		if(!son[p][u])son[p][u] = ++idx;
		p = son[p][u];
	}
	cnt[p]++;
}
bool check(string s ) {
	int p = 0;
	for(int i = 0; i < (int)s.size(); i++) {
		int u = s[i] - 'a';
		if(cnt[p])return false;
		for(int k = 0; k < 26; k++) {
			if(son[p][k] && k != u) {
				g[u].push_back(k);
				d[k]++;
			}
		}
		p = son[p][u];
	}
	return true;
}
bool to(string s) {
	queue<int>q;
	int cnt = 0;
	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 : g[u]) {
			if(!--d[v])q.push(v);
		}
	}
	//cout<
	return cnt == 26;
}
string a[30010];
vector<string>ans;
int cnt1;
void solve() {
	cin >> n;
	fer(i, 1, n)cin >> a[i], insert(a[i]);
	fer(i, 1, n) {
		fer(j, 0, 30) {
			g[j].clear();
			d[j] = 0;
		}
		if(  check(a[i]) &&to(a[i]) ) ans.push_back(a[i]);
	}
	cout << ans.size() << endl;
	for(auto v : ans) {
		cout << v << "\n "[v == ans.back()];
	}
}
int main() {
	IOS;
	int _ = 1;
	//cin>>_;
	while( _-- )
		solve();
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95