为什么会错?
查看原帖
为什么会错?
1037981
封禁用户楼主2024/7/22 16:25
#include<bits/stdc++.h>
using namespace std;
struct node{
	int ch[26],end;
}tree[300004];
int siz=0;
void insert(const string &s){
	int u=0;
	for(char c:s){
		int &v=tree[u].ch[c-'a'];
		if(!v) v=siz++;
		u=v;
	}
	tree[u].end++;
}
vector<int> edge[26];
bool find(const string &s){
	int u=0;
	for(char c:s){
		int t=c-'a';
		if(tree[u].end) return false;
		for(int j=0;j<26;j++){
			if(tree[u].ch[j]&&t!=j) edge[t].push_back(j);
		}
		u=tree[u].ch[t];
	}
	return true;
}
int c[26];
bool dfs(int u){
	c[u]=-1;
	for(int v:edge[u]){
		if(c[v]==-1) return false;
		if(!c[v]&&!dfs(v)) return false;
	}
	c[u]=1;
	return true;
}
bool check(){
	fill_n(c,26,0);
	for(int i=0;i<26;i++){
		if(!c[i]&&!dfs(i)) return false;
	}
	return true;
}
int main(){
	int n;
	cin>>n;
	vector<string> a(n),ans;
	for(int i=0;i<n;i++){
		cin>>a[i];
		insert(a[i]);
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<26;j++){
			edge[j].clear();
		}
		if(find(a[i])&&check()) ans.push_back(a[i]);
	}
	cout<<ans.size()<<'\n';
	for(const string& s:ans) cout<<s<<'\n';
}
2024/7/22 16:25
加载中...