第4题

设整数

n > 1

。山坡上有

n^2

个站点，它们的海拔高度各不相同。两家缆车公司

A

和

B

各自运营

k

条缆车线路；每条缆车线路把乘客从某个站点直接送到更高的站点，中途不停靠。

A

的

k

条缆车线路有

k

个不同的起点和

k

个不同的终点，并且起点越高的缆车，其终点也越高。同样的条件对

B

也成立。如果可以从较低的站点出发，只使用该公司的一条或多条缆车线路（不允许其他任何站点间的移动）到达较高的站点，就说这两个站点被该公司连接。求最小的正整数

k

，使得无论两家公司如何运营，都能保证存在两个同时被两家公司连接的站点。

第 1/8 步：用递增链表示每家公司

通俗地说

起点彼此不同且终点彼此不同，又因所有缆车都向上运行，所以每家公司形成若干条简单的递增路径。

\text{Each company's cars form vertex-disjoint directed paths.}

详细分析

对一家公司而言，每个站点至多是一个缆车的起点，也至多是一个缆车的终点。把每条边从较低站点指向较高站点，则每个顶点的入度和出度都至多为1；又因每条边都严格提高海拔，不可能存在有向环。因此，各连通分量都是互不共享顶点的有向路径，也包括孤立站点。两个站点被该公司连接，当且仅当它们属于同一条路径分量。