题解 CF1889D 【Game of Stacks】

· · 题解

好优雅的题啊 /tyt

首先考虑 c_i = 1 的情况。

转化为图论模型，连边 i \to c_{i, 1}，则 init(i) 的返回值为从 i 开始走到的第一个重复点。

注意到此时的图为内向基环树，于是答案为 i 向上走到的环上第一个点——因为你会在上环后绕一圈回到这里。

乍看没有什么启发性，因为推广到 k_i > 1 的情况后连成的图会长得很抽象。

但注意到对于基环树的情况，我们实际上可以忽略环。对于一般情况，若在中间出现环 v_{i + 1} = c_{v_i, top_i}，则环上的项也可以被类似地消除——即你只要首次走到环上的任意一项，必然都会绕一圈并 pop 掉后回到原点。

于是我们 dfs 时用栈维护走过的点即可。时间复杂度为 O(n + \sum k_i)。

代码：

#include <iostream>
#include <stack>
#include <cstdio>

using namespace std;

int top;
int c[100007], stk[100007], ans[100007];
bool vis[100007];
stack<int> s[100007];

inline int read(){
    int ans = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9'){
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9'){
        ans = ans * 10 + (ch ^ 48);
        ch = getchar();
    }
    return ans;
}

int dfs(int u){
    if (ans[u] != 0) return ans[u];
    if (vis[u]){
        while (true){
            int cur = stk[top--];
            vis[cur] = false;
            s[cur].pop();
            if (cur == u) break;
        }
    }
    vis[u] = true;
    stk[++top] = u;
    if (s[u].empty()) return u;
    return dfs(s[u].top());
}

int main(){
    int n = read();
    for (int i = 1; i <= n; i++){
        int k = read();
        for (int j = 1; j <= k; j++){
            int c = read();
            s[i].push(c);
        }
    }
    for (int i = 1; i <= n; i++){
        if (ans[i] == 0){
            int cur_ans;
            top = 0;
            cur_ans = dfs(i);
            for (int j = 1; j <= top; j++){
                ans[stk[j]] = cur_ans;
            }
        }
        cout << ans[i] << " ";
    }
    return 0;
}