题解：CF1889D Game of Stacks

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

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

直接暴力深搜，建立一个栈 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)

CPP

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 ;
}

题解：CF1889D Game of Stacks

文章操作

相关推荐

评论

题解：CF1889D Game of Stacks