Codeforces Round #711 Two Houses 图论

题意

这是一道交互式的题目。你输出完了他才给你下一次输入。

有一张点数为$n$的有向图。只给你这张图每个点的入度。

这张图里面的任意两点$A$和$B$之间有且仅有一条有向边。目标是找到两个点，使得这两个点在一个环中，且入度差的绝对值尽可能大。

现在，你可以输出任意次不重复查询。每次输出两个点，$A$和$B$。然后他就告诉给你$A$到$B$是否能通。任意一次查询，如果查出来的结果是能通，就不能再有任何查询。

在查询结束之后，你要输出目标要求的两个点。如果整个图没有环，则输出0 0。

题解

先说结论。对于所有可能的两个点的配对（$\frac{n\times(n-1)}{2}$种可能）的入度差的绝对值进行从大到小排序。依次查询这些配对中入度大的到入度小的的点的连通性。如果能联通，则这两个点满足条件。

看一眼下面这张图就很明显了：

我们可以看到，在$B$的所有出度的点中必然至少有一个点是$A$的入度。因此只要入度更大的点能通较小的点就必定成环。

对于入度相等的两个点，其实也是一样。因为$A$到$B$能通会分别占用各自一个出度和一个入度。

代码