人类喜欢用 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?(≤105)，为千手观音留下的数字的个数。随后?N?行，每行给出一个千手观音留下的数字，不超过 10 位数，每一位的符号用不超过 3 个小写英文字母表示，相邻两符号之间用?.?分隔。
我们假设给出的数字顺序在千手观音的世界里是严格递增的。题目保证数字是?104?进制的，即符号的种类肯定不超过?104?种。
输出格式：
在一行中按大小递增序输出符号。当若干根手指之间的相对顺序无法确定时，按它们的英文字典序升序排列。符号间仍然用?.?分隔。
输入样例：
7
pat
cn
lao.cn
lao.oms
pta.lao
pta.pat
cn.pat
输出样例：
lao.pat.pta.cn.oms?题解：读懂题目就会发现是拓扑排序裸题。
坑点：用前向星存图，vector存莫名超时！！！存图需要小点指向大点，大点指向小点建图莫名wrong（当然反过来建图拓扑排序结构不同，可能是要看输出结果来判断，先输出小点，所以需要小点指向大点！！！）；
AC代码：
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int Max=1e5+5;
string str[Max][12];
vector<int>mp[Max];//存图
int ans[Max];//标志是否进优先队列
map<string,int>room;
map<int,string>nex;
char s[12];
vector<int>tmp;//存拓扑排序结果
string ss[Max];
int vis[Max];
int cnt=1;
struct node{
int x;
friend bool operator <(node a,node b){
return nex[a.x]>nex[b.x];
}
};
int main(){
int n;cin>>n;
for(int i=1;i<=n;i++){
scanf("%s",&s);
int len=strlen(s);
for(int j=0;j<len;j++){
if(s[j]=='.') vis[i]++;
else str[i][vis[i]]+=s[j];
}
for(int j=0;j<=vis[i];j++){
if(!room[str[i][j]]){
room[str[i][j]]=cnt;
nex[cnt]=str[i][j];
cnt++;
}
}
if(i!=1&&vis[i]==vis[i-1]){
for(int j=0;j<=vis[i];j++){
if(str[i][j]!=str[i-1][j]){
mp[room[str[i-1][j]]].pb(room[str[i][j]]);
ans[room[str[i][j]]]++;
break;
}
}
}
}
priority_queue<node>q;
node start;
for(int i=1;i<cnt;i++){
start.x=i;
if(ans[i]==0) q.push(start);
}
while(!q.empty()){
start=q.top();
q.pop();
for(int i=0;i<mp[start.x].size();i++){
ans[mp[start.x][i]]--;
if(!ans[mp[start.x][i]]) q.push((node){mp[start.x][i]});
}
cout<<nex[start.x];
if(!q.empty()) cout<<".";
}
}
