GPLT L3-031 千手观音

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

千手观音们的每一根手指都对应一个符号（但是观音世界里的符号太难画了，我们暂且用小写英文字母串来代表），就好像人类用自己的 $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

思路

参考博客： [2022CCCC天梯赛] L3-1 千手观音（30分） - 宇興 - 博客园 (cnblogs.com)

给一些字符串, 被点隔开的是一些变量, 要求确定变量之间的关系, 使其满足所有条件。字符串从小到大给出, 且当前串与上一个串的关系可以确定两个变量的关系。

1:lao.cn
2:lao.oms
3:pta.lao

1串没有前驱, 故跳过比较。接着2串与1串逐位相比, 第一个不同的部分就可以确定一个关系, 即 2串的 mos > 1串的 cn。同理, 3串和2串相比, 可以确定 pta >lao。

题目中又要求不确定关系的变量在结果序列中需要满足按照字典序大小来输出。

一个可行解为： pta > mos > lao > cn

这是一类经典问题：已知若干组大小关系$a_i<a_j$、$a_k>a_l$、$a_p=a_q$，要求构造数列$a$，满足所有给定关系。

这类问题是差分约束系统的简化版：所有边的边权为1或0。若存在相等关系，可以用并查集或Tarjan算法，将所有相等关系缩点。最终均可转化为DAG，拓扑排序即可确定一组最小解（有环则无解）。

故我们就可以通过按顺序边读入边建边, 同时记录入度, 接着求一下拓扑排序就可以。需要注意的是, 题目要求无法确定相对关系的变量需按照字典序递增输出, 可以通过把拓扑排序的队列改为优先队列, 让字典序小且此时入度为0的先处理。

建图时先用无序离散化处理字符串, 比较好建图。