Java教程

D

本文主要是介绍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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!