PTA L3-031 千手观音 (30 分)

人类喜欢用 10 进制，大概是因为人类有一双手 10 根手指用于计数。于是在千手观音的世界里，数字都是 10 000 进制的，因为每位观音有 1 000 双手 ……

千手观音们的每一根手指都对应一个符号（但是观音世界里的符号太难画了，我们暂且用小写英文字母串来代表），就好像人类用自己的 10 根手指对应 0 到 9 这 10 个数字。同样的，就像人类把这 10 个数字排列起来表示更大的数字一样，ta们也把这些名字排列起来表示更大的数字，并且也遵循左边高位右边低位的规则，相邻名字间用一个点 . 分隔，例如 pat.pta.cn 表示千手观音世界里的一个 3 位数。

人类不知道这些符号代表的数字的大小。不过幸运的是，人类发现了千手观音们留下的一串数字，并且有理由相信，这串数字是从小到大有序的！于是你的任务来了：请你根据这串有序的数字，推导出千手观音每只手代表的符号的相对顺序。

注意：有可能无法根据这串数字得到全部的顺序，你只要尽量推出能得到的结果就好了。当若干根手指之间的相对顺序无法确定时，就暂且按它们的英文字典序升序排列。例如给定下面几个数字：

pat
cn
lao.cn
lao.oms
pta.lao
pta.pat
cn.pat

我们首先可以根据前两个数字推断 pat < cn；根据左边高位的顺序可以推断 lao < pta < cn；再根据高位相等时低位的顺序，可以推断出 cn < oms，lao < pat。综上我们得到两种可能的顺序：lao < pat < pta < cn < oms；或者 lao < pta < pat < cn < oms，即 pat 和 pta 之间的相对顺序无法确定，这时我们按字典序排列，得到 lao < pat < pta < cn < oms。

输入格式：
输入第一行给出一个正整数 $N(\le 10^5)$，为千手观音留下的数字的个数。随后 N 行，每行给出一个千手观音留下的数字，不超过 10 位数，每一位的符号用不超过 3 个小写英文字母表示，相邻两符号之间用 . 分隔。

我们假设给出的数字顺序在千手观音的世界里是严格递增的。题目保证数字是 $10^4$ 进制的，即符号的种类肯定不超过 $10^4$种。

输出格式：
在一行中按大小递增序输出符号。当若干根手指之间的相对顺序无法确定时，按它们的英文字典序升序排列。符号间仍然用 . 分隔。

输入样例：

7
pat
cn
lao.cn
lao.oms
pta.lao
pta.pat
cn.pat

输出样例：

lao.pat.pta.cn.oms

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

const int N = 100010;

unordered_map<string,int> d;
unordered_map<string,vector<string>> g;

vector<string> get(string str)
{
    
	vector<string> res;
	string word;
	for(auto &c:str)
	{
    
		if(c=='.')
		{
    
			res.push_back(word);
			if(!d.count(word)) d[word]=0;
			word="";
		}
		else word+=c;
	}
	res.push_back(word);
	if(!d.count(word)) d[word]=0;
	return res;
}

vector<string> topsort()
{
    
	priority_queue<string,vector<string>,greater<string>> Q;
	for(auto &[k,v]:d) 
		if(!v)
			Q.push(k);
	
	vector<string> res;
	while(!Q.empty())
	{
    
		string t=Q.top();Q.pop();
		res.push_back(t);
		for(auto &p:g[t])
			if(--d[p]==0)
				Q.push(p);
	}
	return res;
}

int main()
{
    
	ios::sync_with_stdio(false);
	
	int n;cin>>n;
	string str;cin>>str;
	vector<string> last=get(str);
	
	for(int i=0;i<n-1;i++)
	{
    
		cin>>str;
		vector<string> cur=get(str);
		if(last.size()==cur.size())
		{
    
			for(int j=0;j<(int)cur.size();j++)
				if(last[j]!=cur[j])
				{
    
					g[last[j]].push_back(cur[j]);
					d[cur[j]]++;
					break;
				}
		}
		last=cur;
	}
	
	vector<string> res=topsort();
	cout<<res[0];
	for(int i=1;i<(int)res.size();i++)
		cout<<"."<<res[i];
	return 0;
}