Fox And Names：原题链接

题意：

     题目会给出字符串的个数n经过排序后的字符串，但注意，该字符串排序处于被打乱状态，即不同于正常的字符串排序（a,b,c,d,e......x,y,z），现在请求出打乱后的字典序。

     注：答案不唯一，只要符合题意即可。

做题思路：

     有题意可知，题目需要查找先后，关于先后，优先考虑拓扑排序。

     而本题用拓扑排序的难点在于如何建图，代码如下：

	int minn=min(s1.size(),s2.size());
		//后面需要j的位置,判断两个字符串是否一致 
		int j=0;
		for (;j<minn;j++){
			//查找两个字符串中第一个不同的字符 
			if (s1[j]!=s2[j]) {
				in[s2[j]-'a']++;
				g[s1[j]-'a'].push_back(s2[j]-'a');
				break;
			}
		}

     为什么可以这样写，首先我们需要先了解字符串怎么排序：

     假设我们有两个字符串s1，s2。s1="aa"，s2="z"。而字符串的大小为s1<s2。

     原因是字符串大小排序只取两个字符串中第一个不同的字符，所以，我们可以对比两个字符串中长度较小的一个，遍历两个字符串，并将不同的两个字符作为原拓扑排序的from,to，找到后停止。

     显然这样做还有一个问题，如果出现两个字符串相等，但是s1>sxz2的情况怎么办？那就特判呗。

//倘若j执行到最后且s1的长度>s2的长度
		//说明字符串排序有问题 ，存在环
        if (j==minn && s1.size()>s2.size())return cout <<"Impossible\n",0;
        //使s1继承s2

     在有解决建图问题后，接下来就可以用拓扑排序来判断字典序了，核心代码如下：

bool topu(){
	queue<int>q;
	//从26个字母中查找出入度为0的起点 
	for (int i=0;i<26;i++)
	{
		if (in[i]==0)q.push(i);
	}
	//经典拓扑排序 
	while(!q.empty()) {
		int now=q.front();
		q.pop(); 
		tp.push_back(now);
		for (auto i:g[now]) {
			if (--in[i]==0)q.push(i);
		}
	}
	//判断字典序是否为26
	//否，代表字符序有问题 ，有环存在 
    return tp.size()==26;
}

     处理完以上两点，只要添加上输入和输出，代码就完成了。这里是AC代码：

#include <bits/stdc++.h>
using namespace std;

const int N=105,inf=INT_MAX, M=1e3+10;

int n;
string s1,s2;
int in[N];
vector<int>tp;
vector<int>g[N];

bool topu(){
	queue<int>q;
	//从26个字母中查找出入度为0的起点 
	for (int i=0;i<26;i++)
	{
		if (in[i]==0)q.push(i);
	}
	//经典拓扑排序 
	while(!q.empty()) {
		int now=q.front();
		q.pop(); 
		tp.push_back(now);
		for (auto i:g[now]) {
			if (--in[i]==0)q.push(i);
		}
	}
	//判断字典序是否为26
	//否，代表字符序有问题 ，有环存在 
    return tp.size()==26;
}

int main(){
	cin >>n;
	//为方便输入，采用s1继承s2的形式进行执行 
	cin >>s1;
	for (int i=2;i<=n;i++)
	{
		cin >>s2;
		//因为要遍历字符串，所以选择字符串中最小的长度 
		int minn=min(s1.size(),s2.size());
		//后面需要j的位置,判断两个字符串是否一致 
		int j=0;
		for (;j<minn;j++){
			//查找两个字符串中第一个不同的字符 
			if (s1[j]!=s2[j]) {
				in[s2[j]-'a']++;
				g[s1[j]-'a'].push_back(s2[j]-'a');
				break;
			}
		}
		//倘若j执行到最后且s1的长度>s2的长度
		//说明字符串排序有问题 
        if (j==minn && s1.size()>s2.size())return cout <<"Impossible\n",0;
        //使s1继承s2 
		s1=s2;
	}
	if (topu())
	{
		//将tp数组转换会字符 
		for (int i=0;i<26;i++)cout <<char(tp[i]+'a');
		cout <<"\n";
	}
	else cout <<"Impossible\n";
	return 0;