记录编号	601532	评测结果	AAAAAAAAAA
题目名称	4164.[CF1889D] Game of Stack	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	1.436 s
提交时间	2025-06-25 17:34:07	内存使用	69.61 MiB

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

const int MAXN = 1e5 + 5;
int n,k;
int s[MAXN],index = 0;
stack<int> st[MAXN];
int ans[MAXN];
bool ins[MAXN];

int dfs(int p){
    if(ans[p]) return ans[p];
    if(ins[p])
        while(1){
            int cnt = s[index];
            ins[cnt] = 0;
            st[cnt].pop();
            index --;
            if(p == cnt) break;
        }
    ins[p] = 1;
    s[++ index] = p;
    if(st[p].empty()) return p;
    return dfs(st[p].top());
}

int main(){
	freopen("stack.in","r",stdin);
	freopen("stack.out","w",stdout);
	cin.tie(0) -> ios::sync_with_stdio(0);
    cin >> n;
    for(int i = 1;i <= n;i ++){
        cin >> k;
        for(int j = 1,x;j <= k;j ++){
            cin >> x;
            st[i].push(x);
        }
    }
    for(int i = 1;i <= n;i ++){
        if(!ans[i]){
            index = 0;
            ans[i] = dfs(i);
            for(int j = 1;j <= index;j ++) ans[s[j]] = ans[i];
        }
        cout << ans[i] << ' ';
    }
	return 0;
}