90分,求大佬帮忙看看还有什么地方没考虑到
查看原帖
90分,求大佬帮忙看看还有什么地方没考虑到
401118
Astor楼主2021/10/22 16:19
#include<bits/stdc++.h>
using namespace std;

struct node{
	int num,parent,level;
};
int n;
node Node[105];
int maxlevel=1;
int maxwid=1;

void create(int x,int y,int z){
	int lev=1,wid=1;
	for(int i=0;i<z+1;i++){//依次创建结点 
		if(i>1&&Node[i].level==Node[i-1].level)//找到宽度 
			wid++;
		else{
			if(wid>maxwid){
//				cout<<"  "<<maxwid<<" "<<wid<<endl;
				maxwid=wid;
			}
			wid=1;
		}
		if(Node[i].num==x){//找到深度 
			Node[z].num=y;
			Node[z].parent=i;
			Node[z].level=Node[i].level+1;
			if(Node[z].level>maxlevel)
				maxlevel=Node[z].level;
		}
	}
}

int search(int a,int b){//找两个结点间距离 
	int N,M;
	int ln=1,rn=1;
	for(int i=0;i<n;i++){
		if(Node[i].num==a)
			N=i;
		if(Node[i].num==b)
			M=i;
	}

	while(1){
		if(N==M)
			return 0;
		
		if(Node[N].parent==M)
			return 2*ln;
		if(Node[M].parent==N)
			return rn;
		
		if(Node[N].parent==Node[M].parent){
			return ln*2+rn;
			}
		if(Node[N].level>=Node[M].level){
			
			N=Node[N].parent;
			ln++;
		}
		else{
			M=Node[M].parent;
			rn++;
		}
	}
}

int main(){
	int a,b,c,d;
	cin>>n;//输入结点数 
	Node[0].num=1;//初始化第一个结点 
	Node[0].parent=0;
	Node[0].level=1;
	for(int i=1;i<n;i++){
		cin>>a>>b;
		create(a,b,i);//创建树 
	}
	cout<<maxlevel<<endl<<maxwid<<endl;
	cin>>c>>d;//输入要查找的结点 
	cout<<search(c,d)<<endl;
	return 0;
}
2021/10/22 16:19
加载中...