A company is organizing a meeting and has a list of n employees, waiting to be invited. They have arranged for a large circular table, capable of seating any number of employees. The employees are numbered from 0 to n - 1. Each employee has a favori

maximumInvitations.js

/**
 * @param {number[]} favorite
 * @return {number}
 */
var maximumInvitations = function(favorite) {
    const n = favorite.length;
    let longestCycle = 0; // Variable to track the longest cycle found
    const visit = Array.from({ length: n }, () => false); // Boolean array to track visited nodes
    const len2Cycles = []; // Array to track cycles of length 2

    for (let i = 0; i < n; i++) {
        if (visit[i]) {
            continue;
        }
        
        let start = i;
        let cur = i;
        const curSet = new Set(); // Set to track nodes in the current cycle or chain
        while (!visit[cur]) {
            visit[cur] = true;
            curSet.add(cur);
            cur = favorite[cur];
        }

        if (curSet.has(cur)) {
            let len = curSet.size;
            while (start !== cur) {
                len--;
                start = favorite[start];
            }
            longestCycle = Math.max(longestCycle, len);
            if (len === 2) {
                // If a cycle of length 2 is found, add it to the len2Cycles array
                len2Cycles.push([cur, favorite[cur]]);
            }
        }
    }

    // Create an inverted graph to help with finding chains
    const inverted = {};
    for (let i = 0; i < n; i++) {
        if (inverted[favorite[i]]) {
            inverted[favorite[i]].push(i);
        } else {
            inverted[favorite[i]] = [i];
        }
    }

    // Breadth-first search function to find the length of chains
    function bfs(src, parent) {
        const q = [[src, 0]]; // Queue initialized with the source node and length 0
        let maxLen = 0; // Variable to track the maximum chain length found
        while (q.length > 0) {
            const [node, len] = q.shift();
            if (node === parent) {
                continue;
            }
            maxLen = Math.max(maxLen, len);
            if (inverted[node]) {
                for (let nei of inverted[node]) {
                    q.push([nei, len + 1]);
                }
            }
        }
        return maxLen;
    }

    let chainSum = 0;
    for (let [n1, n2] of len2Cycles) {
        // Sum the lengths of chains connected to cycles of length 2
        chainSum += bfs(n1, n2) + bfs(n2, n1) + 2;
    }

    return Math.max(chainSum, longestCycle);
};