首先,对于读入的数据,我们只需要记录 m 后面的第一个纸条就好了,其后面的,会被其他纸条记录。
比如:纸条 2➡️纸条 1➡️纸条 3。我们只需要记录 2 的 next 是 1 即可,在后面的 1 next 3 不需要记录。因为这个信息会被纸条 1 它自己记录。
由此,题解中的二维 vector 就可以被一个一维数组取代,一个 int a[2005]就足够了。
其次,也是基于上一点。每个纸条都会被在 m 后面读入一次,没读入的就是起点。那么我们只需要在每次读入的时候,先做 sum+=i;然后 sum 减去读入的 next 纸条,最后的sum 就是唯一没被读入的纸条编号,也就是起点。
但是,需要注意的是有结尾“-1”的存在,我们的 sum 要再-1 才是正确结果。
由此,题解中的 vis bool 数组也可以省略,一个 int 变量就能解决。
最后,输出 n 次,先输出 sum,然后下一个点是 sum = a[sum],这样题目就解决了。