BZOJ3012:[Usaco2012 Dec]First! Trie树+Tarjan求强连通分量

思路:一开始的暴力思路是对于每个串,若想使得它成为字典序最小的串,就找到它和任意其他串的从前向后第一个字母不同的位置,并添加限制:这个串的该位置字母的字典序小于其他串的该位置字母的字典序.这样若限制无环,我们就说这个串可以是字典序最小的.

然而这样建图花费的时间太长.

若将所有的串插入一颗Trie树,考虑对于每个串,其需要考虑的限制仅仅是从根节点到串的结尾所对应的节点的路径上的分岔.这样限制数最多为\(O(L*26)\),那么总的限制数最多为\(O(300000*26)\),就可以暴力建图并利用TarjanCheck了.

(为什么没想到Trie树..)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

#define N 30010
#define L 300010

int ch[L][26],cnt,isend[L];
char s[L];int begin[N],len[N];

int G[26][26];
inline void reset(){memset(G,0,sizeof G);}
inline void addedge(int a,int b){/*printf("%d %d\n",a,b);*/G[a][b]=1;}

int dfn[26],low[26],tclock,stk[26],top,num;bool instk[26];
void dfs(int x){
	dfn[x]=low[x]=++tclock;stk[++top]=x,instk[x]=1;
	for(int j=0;j<26;++j)if(G[x][j]){
		if(!dfn[j])dfs(j),low[x]=min(low[x],low[j]);
		else if(instk[j])low[x]=min(low[x],dfn[j]);
	}if(dfn[x]==low[x]){
		++num;
		while(1){int i=stk[top--];instk[i]=0;if(x==i)break;}
	}
}
inline bool judge(){
	memset(dfn,0,sizeof dfn);tclock=top=num=0;memset(instk,0,sizeof instk);
	for(int i=0;i<26;++i)if(!dfn[i])dfs(i);
	return num==26;
}

int ans[N],siz;
int main(){
	int n;cin>>n;
	register int i,j,k;
	int now=0;for(i=1;i<=n;++i)begin[i]=now,scanf("%s",s+now),len[i]=strlen(s+now),now+=len[i];
	int p,y;
	for(i=1;i<=n;++i){
		for(p=0,j=0;j<len[i];++j){if(!ch[p][y=s[begin[i]+j]-'a'])ch[p][y]=++cnt;p=ch[p][y];}
		isend[p]=i;
	}
	for(i=1;i<=n;++i){
		bool notok=0;
		for(reset(),p=0,j=0;j<len[i];p=ch[p][y],++j){
			if(isend[p]&&isend[p]!=i)notok=1;
			y=s[begin[i]+j]-'a';for(k=0;k<26;++k)if(k!=y&&ch[p][k])addedge(y,k);
		}
		if(!notok&&judge())ans[++siz]=i;
	}
	printf("%d\n",siz);
	//for(i=1;i<=siz;++i)printf("%d\n",ans[i]);
	for(i=1;i<=siz;++i){for(j=0;j<len[ans[i]];++j)putchar(s[begin[ans[i]]+j]);puts("");}
	return 0;
}