#1RE,数组模拟树做的,注释齐全,求大佬解决
查看原帖
#1RE,数组模拟树做的,注释齐全,求大佬解决
1288168
silver_rain楼主2024/4/9 11:16
#include<iostream>
#include<vector>
#define noParent 999
using namespace std;
struct Node
{
	int parent;//记录父节点编号
	int layer;//记录所在层,方便求高度和宽度
}node[105];
bool process(int u, int v);
int special[205];//如果当前无法判断u, v谁是父节点或子节点,则记录u, v
int index_special = 0;
int height = 0;
int main()
{
	int i;
	for(i = 0; i <= 104; i++) node[i].parent = noParent;
	int n;
	cin >> n;//n个结点
	node[1].parent = -1;
	node[1].layer = 1;
	for(i = 1; i <= n - 1; i++)
	{
		int u, v;
		cin >> u >> v;
		if(process(u, v))//接下来尝试处理special结点
		{
			vector<int> new_special;
			for(int j = 0; j < index_special; j += 2)
			{
				if(!process(special[j], special[j + 1]))
				{
					new_special.push_back(special[j]);
					new_special.push_back(special[j + 1]);
				}
			}
			index_special = 0;
			while(!new_special.empty())
			{
				special[index_special] = new_special.back();
				new_special.pop_back();
				index_special++;
			}
		}
	}
	int wide = 0;
	int temp_wide[105];
	for(i = 0; i <= 104; i++) temp_wide[i] = 0;
	for(i = 1; i <= n; i++)
		temp_wide[node[i].layer]++;
	for(i = 1; i <= n; i++)
		if(temp_wide[i] > wide) wide = temp_wide[i];
	int node1, node2;
	cin >> node1 >> node2;
  	//原理:记录node1经过的祖先结点,与node2经过的祖先结点一一比较,找到最早相同的祖先结点
	int len1 = 0, len2 = 0;
	int para1[105];
	int para1_index = 0;
	//必须保存node1自己信息,因为可能node1就是node2父节点
	para1[para1_index] = node1;
	para1_index++;
	while(node[node1].parent != -1)
	{
		node1 = node[node1].parent;
		para1[para1_index] = node1;
		para1_index++;
	}
	while(1)
	{
		int flag = 0;
		for(i = 0; i < para1_index; i++)
		{
			if(node2 == para1[i])
			{
				len1 = i;
				flag = 1;
				break;
			}
		}
		if(flag == 1) break;
		len2++;
		node2 = node[node2].parent;
	}
	cout << height << endl << wide << endl << len1 * 2 + len2;
} 
//测试距离 10 7,10 3,8 7均正确
bool process(int u, int v)
{
	int child, paren;
	int temp_index;
  	//判断u,v谁是父节点,谁是子节点
	if(node[u].parent == noParent && node[v].parent != noParent)
	{
		child = u;
		paren = v;
	}
	else if(node[v].parent == noParent && node[u].parent != noParent)
	{
		child = v;
		paren = u;
	}
	else//目前都没父节点
	{
		special[index_special] = u;
		index_special++;
		special[index_special] = v;
		index_special++;
		return false;
	}
	node[child].parent = paren;
	node[child].layer = node[paren].layer + 1;
	if(node[child].layer > height) height = node[child].layer;
	return true;
}

求大佬解答,谢谢!!!

2024/4/9 11:16
加载中...