本文主要是介绍D,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 2e5+10;
int fa[N];
bool isleaf[N];
int get_dis(int x){
int res=0;
while(fa[x]!=x){
res++;
x=fa[x];
}
return res;
}
int print_path(int x){
stack<int> stk;
stk.push(x);
x=fa[x];
while(fa[x]!=x){
stk.push(x);
int tmp=fa[x];
fa[x]=x;
x=tmp;
}
cout<<stk.size()<<endl;
cout<<stk.top();
stk.pop();
while(!stk.empty()){
cout<<" "<<stk.top();
stk.pop();
}
cout<<endl;
}
bool cmp(pii x,pii y){
return x.first>y.first;
}
int main(){
ios::sync_with_stdio(false);
int test;
cin>>test;
while(test--){
int n,a;
vector<pii> lvs;
cin>>n;
//
if(n==1){
cin>>a;
cout<<"1\n1\n1"<<endl;
cout<<endl;
continue;
}
//特判
memset(fa,0,sizeof fa);
memset(isleaf,1,sizeof isleaf);
for(int i=1;i<=n;i++){
cin>>fa[i];
if(i==fa[i]) fa[i]=0;
isleaf[fa[i]]=0;
}
for(int i=1;i<=n;i++){
if(!isleaf[i]) continue;
int dis=get_dis(i);
lvs.push_back({dis,i});
}
sort(lvs.begin(),lvs.end(),cmp);
int len=lvs.size();
cout<<len<<endl;
for(int i=0;i<len;i++){
print_path(lvs[i].second);
}
cout<<endl;
}
return 0;
}
这篇关于D的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!