提出 #75914060

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define eb emplace_back
#define VI vector<int>
#define VII vector<pii>
#define VL vector<ll>
#define VLL vector<pll>
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,r,l) for(int i=(r);i>=(l);--i)

#define LOCAL true

using namespace std;
bool st;
const bool MUL=true;

const int N=3e5+10;
int n,a[N],b[N],in[N],out[N],fa[N],sz[N],D[N];
bool vis[N],act[N];

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y){x=find(x),y=find(y);if(x!=y){if(sz[x]<sz[y])swap(x,y);fa[y]=x,sz[x]+=sz[y];}return;}

void clr(){
	return;
}
void solve(){
	cin>>n;
	rep(i,1,n)cin>>a[i];
	rep(i,1,n)cin>>b[i];
	rep(i,1,n)in[i]=out[i]=D[i]=vis[i]=act[i]=0,fa[i]=i,sz[i]=1;
	rep(i,1,n)out[a[i]]++,in[b[i]]++,vis[a[i]]=vis[b[i]]=1,merge(a[i],b[i]);
	int m=0,rt=0;
	rep(i,1,n)if(vis[i]){
		int r=find(i);
		if(out[i]>in[i])D[r]+=out[i]-in[i];
		if(!act[r])act[r]=1,m++,rt=r;
	}
	if(m==1)cout<<(D[rt]==0?n:n-D[rt])<<"\n";
	else{
		int ans=n;
		rep(i,1,n)if(act[i])ans-=max(1,D[i]);
		cout<<ans<<"\n";
	}
	return; 
}

bool ed;
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int tc=1;if(MUL){cin>>tc;}while(tc--)clr(),solve();
// 	cerr<<"time:"<<clock()<<"ms.\n";
// 	cerr<<fixed<<setprecision(4)<<"memory:"<<(1.0*(&st-&ed)/1048576.0)<<"MB.\n";
	return 0;
}

提出情報

ジャッジ結果