Link
好题，思维量大但是很优雅，鏖战一个晚上无果。
手模两组样例会得到一些小结论，但是没什么用，如果从 \(1 \leq |s_i| \leq 2\) 的角度去入手就会有点眉目（这里记第 \(i\) 个栈为 \(s_i\)）。肯定会很自然地想要去连有向边从 \(i\) 指向 \(top(s_i)\)，从 \(|s_i| = 1\) 开始考虑，注意到此时栈和栈顶所有元素连成的边构成了一个内向基环树。对于环的处理是显然的，我们从第一个接触到的环上节点 \(u\) 进入，绕环一圈 \(pop\) 掉对应的栈顶之后又回到了 \(u\)，这对我们的启发也是显然的，不需要真正去处理环上的节点，绕环修改其对应的栈顶打上标记即可。经过消环之后每棵树的答案就是对应的树根。
考虑 \(|s_i| \gt 1\) 的情况呢？同样的，我们注意到如果当前的局面中出现了环，那么从每一个点出发必定会经过环上的每一个点，又回到环上最初进入环的点，然后连接新边继续遍历。我们在遇到环时每次直接消掉环，更新环中节点栈顶和访问情况，重复这个过程直到出现森林，然后就同上了。由于每棵树的最终答案都是相同的，同时对 \(init(i)\) 的调用互相独立，可以对访问过的节点 \(u\) 进行记忆化，不然很容易写假退化成 \(O(n^2)\) 的。
最终，我们将问题在 \(O(n + \sum k)\) 的时间复杂度下解决。
#include <bits/stdc++.h>using i64 = long long;constexpr int N = 2e5 + 7;int n;
int ans[N], vis[N];std::stack<int> path, stc[N];int dfs(int u) {if (ans[u])return ans[u];if (vis[u]) {while (path.size()) {int v = path.top(); path.pop();vis[v] = 0; stc[v].pop();if (v == u) break;}}vis[u] = 1; path.push(u);if (stc[u].empty())return u;return dfs(stc[u].top());
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cin >> n;for (int i = 1, k; i <= n; i++) {std::cin >> k;for (int j = 1, x; j <= k; j++) {std::cin >> x;stc[i].push(x);}}// std::cout << "1\n";for (int i = 1; i <= n; i++) {if (!ans[i]) {int cur = dfs(i);while (path.size()) {ans[path.top()] = cur;path.pop();}}std::cout << ans[i] << " ";}std::cout << "\n";return 0;
}