Tính chiều cao của cây

[Tuong_Le (Tường Lê)]

Xin chào mọi người, em đang làm bài tính chiều cao của một cây ngẫu nhiên, 1 parent có thể có nhiều hơn 2 Node con (key của nó có data bằng nhau), và được lưu bằng vector. Trong n số có số có data bằng -1 thì nó là root, ngược lại thì 0-based sẽ là root. Cái thuật toán của em nó chạy chậm quá, mọi người xem và gợi ý cho mình với, mình xin cảm ơn nhiều. Hàm cần viết nằm trong \ Replace this code with a faster implementation

// Week1Problem2.cpp : This file contains the 'main' function. Program execution begins and ends there.
#include "pch.h"
#include <iostream>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#if defined(__unix__) || defined(__APPLE__)
#include <sys/resource.h>
#endif
using namespace std;
class Node;

class Node {
public:
	int key;
	Node *parent;
	vector<Node *> children;

	Node() {
		this->parent = NULL;
	}
	void setParent(Node *theParent) {
		parent = theParent;
		parent->children.push_back(this);
	}
};
int main_with_large_stack_space() {
	ios_base::sync_with_stdio(0);
	int n;
	cin >> n;
	vector<Node> nodes;
	nodes.resize(n);
	for (int child_index = 0; child_index < n; child_index++) {
		int parent_index;
		cin >> parent_index;
		if (parent_index >= 0)
			nodes[child_index].setParent(&nodes[parent_index]);
		nodes[child_index].key = child_index;
	}
	// Replace this code with a faster implementation
	
	/*
	int maxHeight = 0;
	for (int leaf_index = 0; leaf_index < n; leaf_index++) {
		int height = 0;
		for (Node *v = &nodes[leaf_index]; v != NULL; v = v->parent)
			height++;
		maxHeight = max(maxHeight, height);
	}
	*/
// allocate save parent key, queue save leaf key
	queue<int> q;
	int maxHeight = 0;
	vector<int> allocate;
	for (int i = 0; i < n; i++)
	{
		Node * temp = &nodes[i];
		if (temp->parent == NULL)
		{
			allocate.push_back(-1);
		}
		else
		{
			if (temp->children.size() == 0)
				q.push(temp->key);
			allocate.push_back(temp->parent->key);
		}
	}
	while (q.empty() == 0)
	{
		int temp = q.front(), height = 0;
		q.pop();
		while (temp != -1)
		{
			temp = allocate[temp];
			height++;
		}
		maxHeight = max(height, maxHeight);
	}
	
	cout << maxHeight;
	return 0;
}

int main(int argc, char **argv)
{
#if defined(__unix__) || defined(__APPLE__)
	// Allow larger stack space
	const rlim_t kStackSize = 16 * 1024 * 1024;   // min stack size = 16 MB
	struct rlimit rl;
	int result;

	result = getrlimit(RLIMIT_STACK, &rl);
	if (result == 0)
	{
		if (rl.rlim_cur < kStackSize)
		{
			rl.rlim_cur = kStackSize;
			result = setrlimit(RLIMIT_STACK, &rl);
			if (result != 0)
			{
				cerr << "setrlimit returned result = " << result << endl;
			}
		}
	}

#endif
	return main_with_large_stack_space();
}

Đây là example:

[Tuong_Le (Tường Lê)]

Mình đã giải ra, mình dùng BFS.

queue<Node*> q;
	int maxHeight = 0;
	Node *root;
	for (int child_index = 0; child_index < n; child_index++)
	{
		Node * temp = &nodes[child_index];
		if (temp->parent == NULL)
		{
			root = temp;
			break;
		}
		
	}
	q.push(root);
	q.push(NULL);
	while (q.empty() == 0)
	{
		Node * temp = q.front();
		q.pop();
		if (temp == NULL && q.size() != 0)
		{
			q.push(NULL);
			maxHeight++;
		}
		else if (temp == NULL && q.size() == 0)
			maxHeight++;
		else if (temp->children.size() != 0)
		{
			vector<Node*> childs = temp->children;
			int run = 0;
			while (run < childs.size())
			{
				q.push(childs[run]);
				run++;
			}
		}
		
	}

[tntxtnt]

dùng dfs vài ba dòng thôi đây

#include <iostream>
#include <vector>
#include <algorithm>

auto height(int s, const std::vector<std::vector<int>>& tree) -> int {
    std::vector<int> childrenHeights;
    std::transform(begin(tree[s]), end(tree[s]), std::back_inserter(childrenHeights),
                   [&](int u) { return height(u, tree); });
    return 1 + (tree[s].empty() ? 0 : *std::max_element(begin(childrenHeights), end(childrenHeights)));
}

auto main() -> int {
    int n = 0;
    std::cin >> n;
    std::vector<std::vector<int>> tree(n);
    int s = 0;
    for (int i = 0, src = 0; i < n; ++i) {
        std::cin >> src;
        if (src == -1) {
            s = i;
        } else {
            tree[src].push_back(i);
        }
    }
    std::cout << height(s, tree);
}

[Tuong_Le (Tường Lê)]

Ahihi để em xem thử, em mới biết BFS chứ chưa biết DFS nữa.

[noname00 (HK boy)]

Tính chiều cao của cây luôn dùng dfs, vì chiều cao của cây = khoảng cách từ gốc đến nút xa nhất.

[kisuluoibieng (Tên Gì Cũng Được)]

BFS (kết hợp queue) thì vẫn tính được chiều cao đó thôi. Bạn hãy vẽ cây ra giấy rồi giải bằng tay đi.