CF1889D Game of Stacks 题解

phoenixzhan · 2024-01-30 10:52:58 · 题解

设在栈顶的数为 a_i，连边 i\to a_i 构成基环内向树。

操作过程可以等价地描述为，从一个起点 u 出发，不断跳出边，同时删掉经过的边，加上 i\to 新的栈顶 a'_i 的边，直到走到一个没有出边的点，这个点就是答案。

注意到，如果当前局面上有环，那么从 每 个 点 出发，必定会经过环上的每一个点，又回到环上走过的一点，同时删去环上的边，加上新边。这等价于直接把环消掉。于是我们可以把环消掉，弹掉对应的栈顶，加上连向新栈顶的边，不断消环直到图变成森林，每个点的答案就容易求了。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define piii tuple<int, int, int>
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define deb(var) cerr << #var << '=' << (var) << "; "
#define int long long
namespace Loser {
    stack<int> a[100010], st;
    int n, ans[100010], vis[100010];
    int dfs(int u) {
        if (ans[u]) return ans[u];
        if (vis[u]) {
            while (1) {
                int v = st.top(); st.pop();
                ans[v] = 0, vis[v] = 0, a[v].pop(); if (v == u) break;
            }
        }
        if (a[u].empty()) return u; 
        st.push(u); vis[u] = 1; return dfs(a[u].top());
    }
    void main() {
        cin >> n;
        for (int i = 1, k, x; i <= n; i++) {
            cin >> k; while (k--) cin >> x, a[i].push(x);
        }
        for (int i = 1; i <= n; i++) {
            ans[i] = dfs(i);
            cout << ans[i] << ' ';
            while (st.size()) ans[st.top()] = ans[i], st.pop();
        } cout << '\n';
    }
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1; while (T--) Loser::main(); return 0;
}