POJ2367【基础】
题目大意:
火星人的亲缘关系系统十分混乱。每个火星人可以有一个或以上的父母,也可
以有很多个子女。现在要安排 N(1<=N<=100)个依次编号为 1 到 N 的火星人按
辈份顺序在一个会议上发言,要求辈份高的先发言。请给出一个发言顺序。
输入:
第一行是一个整数 N。接下来有 N 行,第 i 行有若干个整数,表示第 i 位火星
人的子女的编号,当编号为 0 的时候结束。一个火星人可能没有子女。
输出:
输出一行,包含 N 个整数,为火星人的发言顺序。
题解:
这就是一典型的裸体拓扑排序。除了读入部分,就是数组模拟链表存图+队列优
化的拓扑排序的模板程序。
POJ2585【基础】
题目大意:
有一个 4×4 的窗口,有若干个 2×2 的子窗口会相互覆盖地出现在这个 4×4 的
窗口里。可能出现的子窗口分别编号为 1 到 9,它们有着固定的位置(图此处
略去,请看题目网页)。现在给出一个大窗口的状态图,请判断是否可能出
现。
输入:
输入包含若干组测试数据。每一组测试数据的第一行是“START”,中间是 4×
4 的数字矩阵,最后一行是“END”。当出现一行“ENDOFINPUT”的时候表示所
有测试数据结束。
输出:
每一个测试数据输出一行:如果可以做到,那么输出“THESE WINDOWS ARE
CLEAN”;如果无法做到,输出“THESE WINDOWS ARE BROKEN”。
题解:
通过拓扑排序来找是否有环。建图:对于每一个子窗口(设是第 k 个)所在的
4 个格子,如果某一个格子的数字(设是 l)不是这个子窗口的数字,那么就从
评论0