萌新刚学OI,24pts请求DEBUG
查看原帖
萌新刚学OI,24pts请求DEBUG
922691
Hisy楼主2024/8/20 17:37
#include<bits/stdc++.h>
#define MAXN 30003
#define MAXM 30
using namespace std;
struct node_tree{
	int nxt[MAXM];
	bool end;
}tree[MAXN];
struct node_edge{
	int nxt,to;
}edge[MAXN<<1];
int n,cnt_tree,cnt_edge,tim,top,head[MAXM],dfn[MAXM],low[MAXM];
bool flag,vis[MAXM],matrix[MAXM][MAXM];
string s[MAXN],ans[MAXN];
inline void addedge(int from,int to){
	edge[++cnt_edge].to=to;
	edge[cnt_edge].nxt=head[from];
	head[from]=cnt_edge;
}
inline void insert(string str){
	int root=0;
	for(int i=0;i<str.size();++i){
		int dot=str[i]-'a'+1;
		if(!tree[root].nxt[dot]){
			tree[root].nxt[dot]=++cnt_tree;
		}
		root=tree[root].nxt[dot];
	}
	tree[root].end=true;
}
inline bool prefix(string str){
	int root=0;
	for(int i=0;i<str.size();++i){
		int dot=str[i]-'a'+1;
		if(tree[root].end){
			return false;
		}
		for(int j=1;j<=26;++j){
			if(tree[root].nxt[j]&&dot!=j&&!matrix[dot][j]){
			//	cout<<dot<<' '<<j<<'\n';
				addedge(dot,j);
				matrix[dot][j]=true;
			}
		}
		root=tree[root].nxt[dot];
	}
	return true;
}
inline void tarjan(int now){	
	if(!head[now]){
		return;
	}
	if(flag){
		return;
	}
	low[now]=dfn[now]=++tim;
	vis[now]=true;
	for(int i=head[now];i;i=edge[i].nxt){
		int to=edge[i].to;
		if(!dfn[to]){
			tarjan(to);
			low[now]=min(low[now],low[to]);
		}else if(vis[to]){
			low[now]=min(low[now],low[to]);
		}
		if(flag){
			return;
		}
	}

	if(low[now]==dfn[now]){
	//	cout<<now<<'\n';
		flag=true;
	}
}
int main(){
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>s[i];
		insert(s[i]);
	}
	for(int i=1;i<=n;++i){
		cnt_tree=cnt_edge=tim=0;
		flag=false;
		memset(head,0,sizeof(head));
		memset(edge,0,sizeof(edge));
		memset(low,0,sizeof(low));
		memset(dfn,0,sizeof(dfn));
		memset(vis,0,sizeof(vis));
		memset(matrix,0,sizeof(matrix));
		bool pre=prefix(s[i]);
	//	cout<<cnt_edge<<' '<<pre<<' ';
		for(int j=1;j<=26;++j){
			if(!dfn[j]){
				tarjan(j);
			}
		}
	//	cout<<flag<<'\n';
		if(pre&&!flag){
			ans[++top]=s[i];
		}
	}
	cout<<top;
	for(int i=1;i<=top;++i){
		cout<<'\n'<<ans[i];
	}
	return 0;
}
2024/8/20 17:37
加载中...