CF510C

标签：s2 s1 CF510C 字符串 Impossible 字典

其实是一道板子题，建议评黄。

题意

求一种满足让\(n\)个字符串合法排列的字典序。

思路

不难想到使用拓扑排序。

具体地说，我们可以把字符串当作点，若有两个字符串 \(s1,s2\) 且满足 \(s1\) 的字典序小于 \(s2\) ，则建一条从 \(s1\) 到 \(s2\) 的边。

注意到如果有两个字符串 \(s2\) 为 \(s1\) 前缀且 \(s1\) 在 \(s2\) 前面，那么无论如何改变字典序，同样的字符都是一样长的，而长的显然在后边，所以输出 Impossible。

又注意到图有环也显然不可能，所以所以有环也输出 Impossible。

最后放一段核心代码:

for(int i=1;i<=26;i++)if(cnt[i]==0)q.push(i);
while(!q.empty()){
	int head=q.front();
	ans[sum]=head;
	sum++;
	q.pop();
	for(int i=1;i<=cnt[head];i++){
	cnt[a[head][i]]--;
	if(!cnt[a[head][i]])
		q.push(a[head][i]);
	}		
}

标签：s2,s1,CF510C,字符串,Impossible,字典
From： https://www.cnblogs.com/JacoAwA/p/CF510C.html