啊啊啊每次补完题都感觉这题我场上应该是能想出来的啊!
考虑简化问题:若每个栈内只有一个元素,how。
此时我们发现所有栈之间构成了一个内向基环树。且环是没有用的,因为我们在环上走一圈之后仍然会回到原点。所以不妨把所有环边删除,此时每棵树的答案即为树根。
而对于原问题,同理,我们可以考虑不断找环,每找到一个环就回溯到对应点,继续向后找,只要我们能保证每个元素只被我们找到 \(O(1)\) 次,时间复杂度就可以做到 \(O(n+\sum k)\) 量级。
弱化问题,简化问题。
标签:CF1889D,我们,问题,Game,简化,Stacks From: https://www.cnblogs.com/ydtz/p/17797211.html