题解：CF1889D Game of Stacks

wallace_QwQ · 2025-02-22 01:39:35 · 题解

发现其他题解都没有仔细地讲解实现。

所以特地来补充一下造福后人。

直接暴力深搜，建立一个栈 st，每遍历到一个栈，就将栈的编号塞入 st 中。

如果第 i 个栈的栈顶为 c_{i,j}，那么就建立一条 i\to c_{i,j} 的边，并走过去。

此时有四种情况

• 第 c_{i,j} 个栈已经为空，那么所有留存在 st 中的栈的答案均为 c_{i,j}
• 第 c_{i,j} 个栈已经记录了答案 ans_{c_{i,j}}，那么所有留存在 st 中的栈的答案均为 ans_{c_{i,j}}
• 第 c_{i,j} 个栈已经被遍历过了，那么对 st 进行弹栈操作直到 c_{i,j} 被弹出，对于每个被弹出的栈的编号 st_i，我们将第 st_i 个栈的栈顶永久性的弹出（因为显然此时构成了一个环，无论你从这个环的哪一处开始遍历，这一个环都一定会被消去）。
• 否则，继续搜索。

显然总复杂度为 O(n+\sum k_i)

int n,k[N],ans[N];
stack<int> c[N],st;
bool vis[N];
int dfs(int u){
    if(ans[u]) return ans[u];
    if(vis[u])
        while(1){
            int v=st.top(); st.pop();
            vis[v]=0;
            c[v].pop();
            if(v==u) break;
        }
    vis[u]=1,st.push(u);
    if(c[u].empty()) return u;
    return dfs(c[u].top());
}
void solve(){
    cin>>n;
    for1(i,1,n){
        cin>>k[i];
        for1(j,1,k[i]){
            int _c;
            cin>>_c;
            c[i].push(_c);
        }
    }
    for1(i,1,n){
        if(!ans[i]){
            ans[i]=dfs(i);
            while(!st.empty())
                ans[st.top()]=ans[i],st.pop();
        }
        cout<<ans[i]<<" ";
    }
    return ;
}