CF1889D Game of Stacks 题解

link T3です

有 $n$ 个整数栈 $s_1, s_2, \dots, s_n$ 。

对于一个初始值 $p$ ，令 $x_p$ 为 $s_p$ 的栈顶，更新 $p\leftarrow x_p$ ，直到 $s_p$ 为空。

对每个 $p = 1, 2, \dots, n$ ，求最终的 $p$ 值。

优雅。

先考虑栈大小为 $1$ 的情况。

我们考虑直接转化为图论模型。即连边 $i\rightarrow x_i$ 。

注意到这里实际上是一个内向基环树。那么对于任意出发点 $p$ 而言，结果就为走到环上的第一个点。

乍看没有什么启发性。因为栈大小 $>1$ 的情况很难建图。

但注意到对于基环树的情况，我们实际上可以忽略环。

容易发现，一个环上的所有点转一圈也都是回到自己的点。就说明忽略环对所有 $p$ 不会影响正确性。

这个东西也可以应用到栈大小 $>1$ 的情况：

考虑对每个 $p$ 跑一遍，在跑的过程中遇到的环是可以直接从栈里面抹除的。那么抹除了所有环之后这些栈构成的边就会变成一棵树。直接在树上跑一遍即可。

分析一下复杂度。 $O(\sum k+n^2)$ ，咦，超了。

这里复杂度有 $O(n^2)$ 的原因是每个点都有可能遍历一遍整棵树。

那么我们可以考虑 $p$ ， $ans_p=t$ ，显然 $p$ 在树上经过的点最后的结果都为 $t$ 。只对没有 $ans$ 的位置访问和转移即可。

代码如下：

int n;
vector<int> a[maxn];
void input(){
	n=read();
	for(int i=1;i<=n;++i){
		int len=read();
		a[i].emplace_back(0);
		for(int j=1;j<=len;++j){
			a[i].emplace_back(read());
		}
	}
}

int ans[maxn];

int vis[maxn],top[maxn];
int tim;
stack<pair<int,int> > fix;//在时间tim修改了哪个位置
int go(int st){
	int x=st;
	while(1){
		vis[x]=++tim;
		fix.push({tim,x});

		int nxt=a[x][top[x]];
		--top[x];
		if(ans[nxt]) return ans[nxt];
		if(vis[nxt]){
			int previstim=vis[nxt];
			while(fix.size()&&fix.top().first>=previstim){
				int p=fix.top().second;
				a[p].pop_back();//至于这里为什么可以直接 pop_back 看下面
				vis[p]=0;
				fix.pop();
			}
			tim=previstim-1;
		}
		if(nxt==0) return x;
		x=nxt;
	}
}
void solve(){
	for(int i=1;i<=n;++i){
		top[i]=a[i].size()-1;
	}
	for(int i=1;i<=n;++i){
		if(!ans[i]){
			int endp=go(i);
			while(fix.size()){
				int p=fix.top().second;
				++top[p];
				ans[p]=endp;
				vis[p]=0;
				fix.pop();
			}
			tim=0;
		}
	}
	for(int i=1;i<=n;++i) printf("%d ",ans[i]);
}

int main(){
	input();
	solve();
	return 0;
}