agent.md

agent.md

Soit un fichier de la forme

4
7 4
4 0
3 4
8 3

Signifiant :

• 4 lignes (4 + 1 noeuds dans l'arbre)
• Le parent du noeud 7 est le noeud 4
• Le parent du noeud 4 est le noeud 0 etc, le neoud 0 étant la racine de l'arbre

Trouver le nombre de noeuds par niveau. Le noeud 0 étant au niveau 1. (Dans cet exemple : 1 noeud de niveau 1, 1 de niveau 2, 2 de niveau 3, 1 de niveau 4)

Le fichier a été lu et input représente la lecture du fichier ligne par ligne.

function ensureHasLevel(agents, agent) {
    if (agents[agent].level !== undefined) return;
    
    const chief = agents[agent].chief;
    
    ensureHasLevel(agents, chief);
    agents[agent].level = agents[chief].level + 1;
}

function ContestResponse(){
    agents = {};
    
    agents[0] = { 'level': 1, 'chief': undefined };
    
    for (let i = 1 ; i != input.length ; ++i) {
        const [agentId, chief] = input[i].split(' ');
        agents[agentId] = { 'level': undefined, 'chief': chief }
    }
    
    for (let agent in agents) {
        ensureHasLevel(agents, agent)
    }
    
    let levels = [];
    for (let i = 0 ; i != 10 ; ++i) levels.push(0);
    
    for (let agent in agents) {
        levels[agents[agent].level - 1] += 1;
    }
    
    
    let s = "";
    
    for (let level of levels) {
        s += level;
        s += " ";
    }
    
    console.log(s);
}

Complexité : O(n)