标题的意思是,你需要实现下面这题的自适应交互库:
交互题。有一堆未知数 a1a_1a1 到 ana_nan 互不相同,你需要给出它们的排序。你获取信息的方式只有调用 compare(i,j) 来得到 aia_iai 和 aja_jaj 的大小关系。
compare(i,j)
此处假设对于未被此前的询问确定的大小关系一律随机返回一个值。
实际上等价于下面的表述:
维护一个 nnn 个点的有向图,初始为空。支持增加一条边,或者查询两个点之间是否有一条单向路及其方向。保证图永远无环。