看到排列并且有 \(i\gets a_i\)，就可以直接建出图来，显然是若干个不相干的环。
如果不求字典序最小，就可以直接不在同一个环中的 \(i,j\) 直接交换就可以了，因为它要求了最小化操作数。如果求字典序最小，直接从前往后扫一遍，可以用 set 维护不在这个环中且 \(j>i\) 的最小值，如果小于当前的 \(a_i\) 就可以直接交换。但注意如果这是这个环的最后一个数，就必须要交换。
时间复杂度：\(\mathcal{O}(n\log n)\)。空间线性。
更优的做法是因为最小值有单调性，就可以不用 set，直接扫一遍即可。
代码：
const int N=2e5+10;
int n;
int a[N],fa[N],sz[N],mn[N],pos[N];
set<pii> s;
typedef set<pii>::iterator iter;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merg(int u,int v){
u=find(u),v=find(v);
if(u!=v){
fa[u]=v,sz[v]+=sz[u];
s.erase(pii(mn[u],u));
s.erase(pii(mn[v],v));
s.insert(pii((mn[v]=min(mn[u],mn[v])),v));
}
}
void solve(){
cin>>n;
s.clear();
for(int i=1;i<=n;i++)cin>>a[i],fa[i]=mn[i]=i,pos[a[i]]=i,sz[i]=1,s.insert(pii(mn[i],i));
for(int i=1;i<=n;i++)merg(a[i],i);
for(int i=1;i<=n&&s.size()>1;i++){
iter it=s.begin();
while(find(it->second)==find(i))it++;
int v=it->first,p=pos[it->first];
if(v<a[i]||sz[find(i)]==1){
swap(a[i],a[p]);swap(pos[a[i]],pos[a[p]]);
merg(i,p);
}
sz[find(i)]--;
}
for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<"\n";
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int T;cin>>T;
while(T--)solve();
return 0;
}