C++(g++ 7.5.0) 解法, 执行用时: 34ms, 内存消耗: 3168K, 提交时间: 2022-09-16 15:43:38

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=5e5;
ll s[maxn+5],p[maxn+5],vis[maxn+5];
int main(){
	ll n,m,i,j,k,ans=0,dq;
	scanf("%lld%lld",&n,&m);
	for(i=1;i<=n;i++) scanf("%lld",&s[i]);
	for(i=1;i<=n;i++){
		if(vis[i]==1) continue;
		dq=i;
		while(vis[dq]==0){
			vis[dq]=1,dq=s[dq];
		}
		ans++;
	}
	if(ans-m>=2) printf("%lld\n",ans-m);
	else{
		if((ans-1)%2==m%2) puts("1");
		else puts("2");
	}
	return 0;
}

C 解法, 执行用时: 30ms, 内存消耗: 1676K, 提交时间: 2022-06-04 14:27:31

#include <stdio.h>

int a[200005],b[200005];

int main(){
	int n,i,m,j,max,k,h;
	int t=0;
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(i=1;i<=n;i++){
		if(b[i]==0){
			b[i]=1;
			k=a[i];
			while(b[k]==0){
				b[k]=1;
				k=a[k];
			}
			t++;
		}
	}
	if(m<t)
		printf("%d",t-m);
	else{
		if((m-t+1)%2==0)
			printf("1");
		else
			printf("2");
	}
	return 0;
}

C++ 解法, 执行用时: 53ms, 内存消耗: 1784K, 提交时间: 2022-06-04 17:01:17

#include<bits/stdc++.h>
using namespace std;
int cnt, n, k, a[212345], v[212345];
void dfs(int n)
{
	if(v[a[n]])
		return;
	v[a[n]] = 1;
	dfs(a[n]);
}
signed main()
{
	cin >> n >> k;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 1; i <= n; i++)
		if(!v[a[i]])
			cnt++, dfs(i);
	while(k--)
		if(cnt > 1)
			cnt--;
		else
			cnt++;
	cout << cnt; 
}