Max Height Calculation — Problem Statement & Solution Guide

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

int maxHeight(unordered_map<int, vector<int>>& children, int root) {
    if (children.find(root) == children.end() || children[root].empty()) {
        return 1;
    }
    
    int maxChildHeight = 0;
    for (int child : children[root]) {
        int childHeight = maxHeight(children, child);
        maxChildHeight = max(maxChildHeight, childHeight);
    }
    
    return 1 + maxChildHeight;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    cin >> N;
    
    unordered_map<int, vector<int>> children;
    unordered_set<int> allNodes;
    unordered_set<int> childNodes;
    
    for (int i = 0; i < N; i++) {
        int node, C;
        cin >> node >> C;
        vector<int> kids(C);
        for (int j = 0; j < C; j++) {
            cin >> kids[j];
            childNodes.insert(kids[j]);
        }
        children[node] = kids;
        allNodes.insert(node);
    }
    
    int root = -1;
    for (int node : allNodes) {
        if (childNodes.find(node) == childNodes.end()) {
            root = node;
            break;
        }
    }
    
    cout << maxHeight(children, root) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    public static int maxHeight(Map<Integer, List<Integer>> children, int root) {
        if (!children.containsKey(root) || children.get(root).isEmpty()) {
            return 1;
        }
        
        int maxChildHeight = 0;
        for (int child : children.get(root)) {
            int childHeight = maxHeight(children, child);
            maxChildHeight = Math.max(maxChildHeight, childHeight);
        }
        
        return 1 + maxChildHeight;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        
        Map<Integer, List<Integer>> children = new HashMap<>();
        Set<Integer> allNodes = new HashSet<>();
        Set<Integer> childNodes = new HashSet<>();
        
        for (int i = 0; i < N; i++) {
            int node = scanner.nextInt();
            int C = scanner.nextInt();
            List<Integer> kids = new ArrayList<>();
            for (int j = 0; j < C; j++) {
                int child = scanner.nextInt();
                kids.add(child);
                childNodes.add(child);
            }
            children.put(node, kids);
            allNodes.add(node);
        }
        
        int root = -1;
        for (int node : allNodes) {
            if (!childNodes.contains(node)) {
                root = node;
                break;
            }
        }
        
        System.out.println(maxHeight(children, root));
        scanner.close();
    }
}

import sys

def max_height(children, root):
    if root not in children or len(children[root]) == 0:
        return 1
    
    max_child_height = 0
    for child in children[root]:
        child_height = max_height(children, child)
        max_child_height = max(max_child_height, child_height)
    
    return 1 + max_child_height

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    
    def read_int():
        nonlocal idx
        val = int(input_data[idx])
        idx += 1
        return val
    
    N = read_int()
    children = {}
    all_nodes = set()
    child_nodes = set()
    
    for _ in range(N):
        node = read_int()
        C = read_int()
        kids = []
        for _ in range(C):
            child = read_int()
            kids.append(child)
            child_nodes.add(child)
        children[node] = kids
        all_nodes.add(node)
    
    root = -1
    for node in all_nodes:
        if node not in child_nodes:
            root = node
            break
    
    print(max_height(children, root))

if __name__ == "__main__":
    main()

function maxHeight(children, root) {
    if (!children[root] || children[root].length === 0) {
        return 1;
    }
    
    let maxChildHeight = 0;
    for (const child of children[root]) {
        const childHeight = maxHeight(children, child);
        maxChildHeight = Math.max(maxChildHeight, childHeight);
    }
    
    return 1 + maxChildHeight;
}

const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split('\n');
let index = 0;

function readInt() {
    return parseInt(data[index++]);
}

const N = readInt();
const children = {};
const allNodes = new Set();
const childNodes = new Set();

for (let i = 0; i < N; i++) {
    const node = readInt();
    const C = readInt();
    const kids = [];
    for (let j = 0; j < C; j++) {
        const child = readInt();
        kids.push(child);
        childNodes.add(child);
    }
    children[node] = kids;
    allNodes.add(node);
}

let root = -1;
for (const node of allNodes) {
    if (!childNodes.has(node)) {
        root = node;
        break;
    }
}

console.log(maxHeight(children, root));