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

#include <bits/stdc++.h>
using namespace std;

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

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(){
    freopen("stack.in","r",stdin);
    freopen("stack.out","w",stdout);
	scanf("%d",&n);
	for (int i = 1; i <= n; i++){
		scanf("%d",&k);
		for (int j = 1; j <= k; j++){
			int c;
			scanf("%d",&c);
			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;
}