题解 [蓝桥杯 2016 省 B] 交换瓶子

题目链接

本题解讲解环图的做法。

要将一个 \(1\sim n\) 的排列通过交换变成 \(1\sim n\)，可以先将 \(i\) 向 \(a_i\) 连边，那么最终一定会练成若干个环（每个点只有一个出度，也只有一个入度）。

假设交换在同一个环中的节点，一个环显然会变成两个环，也就是说，交换一次最多增加一个环的数量，那么最终要求显然是 \(n\) 个环的情况，即 \(n\) 个自环，求出环的数量 \(cnt\)，答案就是 \(n-cnt\)。

代码：

const int N=11000;
int n,a[N],to[N],vis[N];

int main() {
	cin>>n;
	for(int i=1;i<=n;i++) {
		int x; cin>>x;
		to[i]=x;
	}
	int ans=0;
	for(int i=1;i<=n;i++) {
		if(vis[i]) continue;
		ans++;
		for(int j=i;!vis[j];j=to[j]) {
			vis[j]=1;
		}
	}
	cout<<n-ans;

	return 0;
}