Maximum Employees to Be Invited to a Meeting

Maximum Employees to Be Invited to a Meeting - Problem

A company is organizing a meeting with n employees around a large circular table. Each employee has exactly one favorite person they want to sit next to, and they'll only attend if this condition is met.

Think of this as a graph problem where each employee points to their favorite person, creating a functional graph (each node has exactly one outgoing edge). The challenge is to find the maximum number of employees we can invite while satisfying everyone's seating preferences.

Key insights:

Since it's a circular table, we can have cycles of any length
We can also have "chains" that lead into cycles
For cycles of length > 2, we can only invite the cycle members
For cycles of length 2 (mutual favorites), we can extend with chains leading to them

Goal: Return the maximum number of employees that can be invited to the meeting.

Input & Output

example_1.py — Basic 2-cycles

$ Input: [2,2,1,2]

› Output: 3

💡 Note: Employee 1 and 2 are mutual favorites (1→2, 2→1). Employee 0 favorites employee 2, so we can seat them as 0→2↔1, creating a chain of length 3. Employee 3 also favorites 2, but we can only extend one side of the 2-cycle.

example_2.py — Large cycle

$ Input: [1,2,0]

› Output: 3

💡 Note: We have a 3-cycle: 0→1→2→0. Since this is a cycle of length > 2, we can invite all 3 employees and seat them in this exact circular order.

example_3.py — Multiple 2-cycles with chains

$ Input: [3,0,1,4]

› Output: 4

💡 Note: We have one 2-cycle: 0↔3 (0→3, 3→0). Employees 1 and 2 form a separate 2-cycle: 1→2→1. Wait, that's not right. Let me recalculate: 0→3, 1→0, 2→1, 3→4. This creates: 2→1→0↔3→4, but 4 would need to point somewhere. Let me use a simpler example.

Constraints

n == favorite.length
2 ≤ n ≤ 10⁵
0 ≤ favorite[i] ≤ n - 1
favorite[i] != i (no self-favorites)

Visualization

Tap to expand

Understanding the Visualization

Identify Graph Type

Each employee points to exactly one favorite - this creates a functional graph

Find Cycles

Every connected component must eventually form a cycle

Classify Cycles

Large cycles (>2) vs 2-cycles (mutual pairs)

Extend 2-Cycles

2-cycles can be extended with incoming chains

Choose Maximum

Pick either the largest single cycle or sum of all extended 2-cycles

Key Takeaway

🎯 Key Insight: In a functional graph, we can either invite one complete large cycle OR multiple 2-cycles extended with their incoming chains - never mix both approaches!

Asked in

G Google 15 a Amazon 8 f Meta 12 ⊞ Microsoft 6

This problem is about finding cycles in a functional graph where each node has exactly one outgoing edge. The optimal solution recognizes that we can either invite one large cycle (length > 2) OR combine all 2-cycles with their incoming chains. Use DFS to detect cycles and topological analysis to find chain lengths.

Common Approaches

Approach	Time	Space	Notes
✓ Graph Analysis with DFS	O(n²)	O(n)	Find all cycles and chains in the functional graph using depth-first search

Graph Analysis with DFS — Algorithm Steps

Build the graph and reverse graph (incoming edges)
Use DFS to find all cycles in the graph
For each 2-cycle, find the longest chains leading to both nodes
For cycles of length > 2, we can only take the cycle itself
Return maximum of: largest cycle, or sum of all 2-cycles with their chains

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Create adjacency lists and reverse graph

Find Cycles

Use DFS to detect all cycles in the graph

Analyze Structure

Classify cycles as 2-cycles or larger cycles

Calculate Maximum

Choose between single large cycle or multiple 2-cycles with chains

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define MAX_N 1000

typedef struct {
    int* data;
    int size;
    int capacity;
} IntList;

IntList* createList() {
    IntList* list = malloc(sizeof(IntList));
    list->capacity = 10;
    list->data = malloc(list->capacity * sizeof(int));
    list->size = 0;
    return list;
}

void addToList(IntList* list, int value) {
    if (list->size >= list->capacity) {
        list->capacity *= 2;
        list->data = realloc(list->data, list->capacity * sizeof(int));
    }
    list->data[list->size++] = value;
}

int longestChainTo(int node, bool* excludeSet, IntList* incoming[], int n);

int maximumInvitations(int* favorite, int favoriteSize) {
    int n = favoriteSize;
    
    // Build reverse graph
    IntList* incoming[MAX_N];
    for (int i = 0; i < n; i++) {
        incoming[i] = createList();
    }
    
    for (int i = 0; i < n; i++) {
        addToList(incoming[favorite[i]], i);
    }
    
    bool visited[MAX_N] = {false};
    IntList cycles[MAX_N];
    int cycleCount = 0;
    
    // Find cycles (simplified)
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            int path[MAX_N];
            int pathLen = 0;
            int current = i;
            
            // Follow path until cycle or visited node
            while (!visited[current] && pathLen < n) {
                path[pathLen++] = current;
                current = favorite[current];
            }
            
            // Check if we found a cycle
            bool foundCycle = false;
            int cycleStart = -1;
            for (int j = 0; j < pathLen; j++) {
                if (path[j] == current) {
                    foundCycle = true;
                    cycleStart = j;
                    break;
                }
            }
            
            if (foundCycle) {
                cycles[cycleCount] = *createList();
                for (int j = cycleStart; j < pathLen; j++) {
                    addToList(&cycles[cycleCount], path[j]);
                }
                cycleCount++;
            }
            
            // Mark all nodes in path as visited
            for (int j = 0; j < pathLen; j++) {
                visited[path[j]] = true;
            }
        }
    }
    
    // Case 1: Single large cycle
    int maxSingleCycle = 0;
    for (int i = 0; i < cycleCount; i++) {
        if (cycles[i].size > 2) {
            maxSingleCycle = maxSingleCycle > cycles[i].size ? maxSingleCycle : cycles[i].size;
        }
    }
    
    // Case 2: Multiple 2-cycles with chains
    int totalTwoCycles = 0;
    for (int i = 0; i < cycleCount; i++) {
        if (cycles[i].size == 2) {
            int a = cycles[i].data[0];
            int b = cycles[i].data[1];
            
            bool excludeSet[MAX_N] = {false};
            excludeSet[a] = true;
            excludeSet[b] = true;
            
            int chainToA = longestChainTo(a, excludeSet, incoming, n);
            int chainToB = longestChainTo(b, excludeSet, incoming, n);
            totalTwoCycles += 2 + chainToA + chainToB;
        }
    }
    
    return maxSingleCycle > totalTwoCycles ? maxSingleCycle : totalTwoCycles;
}

int longestChainTo(int node, bool* excludeSet, IntList* incoming[], int n) {
    int maxLength = 0;
    for (int i = 0; i < incoming[node]->size; i++) {
        int prev = incoming[node]->data[i];
        if (!excludeSet[prev]) {
            bool newExclude[MAX_N];
            memcpy(newExclude, excludeSet, n * sizeof(bool));
            newExclude[prev] = true;
            
            int length = 1 + longestChainTo(prev, newExclude, incoming, n);
            maxLength = maxLength > length ? maxLength : length;
        }
    }
    return maxLength;
}

int main() {
    int n;
    printf("Enter size: ");
    scanf("%d", &n);
    
    int favorite[MAX_N];
    printf("Enter array: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &favorite[i]);
    }
    
    printf("%d\n", maximumInvitations(favorite, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

DFS traversal is O(n), but we might do this for multiple starting points and check various combinations

⚠ Quadratic Growth

Space Complexity

O(n)

Space for visited arrays, recursion stack, and storing cycles/chains

⚡ Linearithmic Space

26.2K Views

Medium Frequency

~35 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Graph Analysis with DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler