Question

2127. Maximum Employees to Be Invited to a Meeting

中文文档

Description

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 favorite person and they will attend the meeting only if they can sit next to their favorite person at the table. The favorite person of an employee is not themself.

Given a 0-indexed integer array favorite, where favorite[i] denotes the favorite person of the ith employee, return _the maximum number of employees that can be invited to the meeting_.

 

Example 1:

Input: favorite = [2,2,1,2]
Output: 3
Explanation:
The above figure shows how the company can invite employees 0, 1, and 2, and seat them at the round table.
All employees cannot be invited because employee 2 cannot sit beside employees 0, 1, and 3, simultaneously.
Note that the company can also invite employees 1, 2, and 3, and give them their desired seats.
The maximum number of employees that can be invited to the meeting is 3. 

Example 2:

Input: favorite = [1,2,0]
Output: 3
Explanation: 
Each employee is the favorite person of at least one other employee, and the only way the company can invite them is if they invite every employee.
The seating arrangement will be the same as that in the figure given in example 1:
- Employee 0 will sit between employees 2 and 1.
- Employee 1 will sit between employees 0 and 2.
- Employee 2 will sit between employees 1 and 0.
The maximum number of employees that can be invited to the meeting is 3.

Example 3:

Input: favorite = [3,0,1,4,1]
Output: 4
Explanation:
The above figure shows how the company will invite employees 0, 1, 3, and 4, and seat them at the round table.
Employee 2 cannot be invited because the two spots next to their favorite employee 1 are taken.
So the company leaves them out of the meeting.
The maximum number of employees that can be invited to the meeting is 4.

 

Constraints:

• n == favorite.length
• 2 <= n <= 105
• 0 <= favorite[i] <= n - 1
• favorite[i] != i

Solutions

Solution 1: Maximum Cycle in Graph + Longest Chain

We observe that the employee's preference relationship in the problem can be regarded as a directed graph, which can be divided into multiple "base cycle inward trees". Each structure contains a cycle, and each node on the cycle is connected to a tree.

What is a "base cycle inward tree"? First, a base cycle tree is a directed graph with $n$ nodes and $n$ edges, and an inward tree means that in this directed graph, each node has exactly one outgoing edge. In this problem, each employee has exactly one favorite employee, so the constructed directed graph can be composed of multiple "base cycle inward trees".

For this problem, we can find the length of the maximum cycle in the graph. Here we only need to find the length of the largest cycle, because if there are multiple cycles, they are not connected to each other, which does not meet the problem requirements.

In addition, for the size of the cycle equal to $2$, that is, there are two employees who like each other, then we can arrange these two employees together. If these two employees are each liked by other employees, then we only need to arrange the employees who like them next to them. If there are multiple such situations, we can arrange them all.

Therefore, the problem is actually equivalent to finding the length of the maximum cycle in the graph, and all cycles of length $2$ plus their longest chain. The maximum of these two can be found. To find the longest chain to the cycle of length $2$, we can use topological sorting.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array favorite.

class Solution:
  def maximumInvitations(self, favorite: List[int]) -> int:
    def max_cycle(fa: List[int]) -> int:
      n = len(fa)
      vis = [False] * n
      ans = 0
      for i in range(n):
        if vis[i]:
          continue
        cycle = []
        j = i
        while not vis[j]:
          cycle.append(j)
          vis[j] = True
          j = fa[j]
        for k, v in enumerate(cycle):
          if v == j:
            ans = max(ans, len(cycle) - k)
            break
      return ans

    def topological_sort(fa: List[int]) -> int:
      n = len(fa)
      indeg = [0] * n
      dist = [1] * n
      for v in fa:
        indeg[v] += 1
      q = deque(i for i, v in enumerate(indeg) if v == 0)
      while q:
        i = q.popleft()
        dist[fa[i]] = max(dist[fa[i]], dist[i] + 1)
        indeg[fa[i]] -= 1
        if indeg[fa[i]] == 0:
          q.append(fa[i])
      return sum(dist[i] for i, v in enumerate(fa) if i == fa[fa[i]])

    return max(max_cycle(favorite), topological_sort(favorite))

class Solution {
  public int maximumInvitations(int[] favorite) {
    return Math.max(maxCycle(favorite), topologicalSort(favorite));
  }

  private int maxCycle(int[] fa) {
    int n = fa.length;
    boolean[] vis = new boolean[n];
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      if (vis[i]) {
        continue;
      }
      List<Integer> cycle = new ArrayList<>();
      int j = i;
      while (!vis[j]) {
        cycle.add(j);
        vis[j] = true;
        j = fa[j];
      }
      for (int k = 0; k < cycle.size(); ++k) {
        if (cycle.get(k) == j) {
          ans = Math.max(ans, cycle.size() - k);
        }
      }
    }
    return ans;
  }

  private int topologicalSort(int[] fa) {
    int n = fa.length;
    int[] indeg = new int[n];
    int[] dist = new int[n];
    Arrays.fill(dist, 1);
    for (int v : fa) {
      indeg[v]++;
    }
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; ++i) {
      if (indeg[i] == 0) {
        q.offer(i);
      }
    }
    int ans = 0;
    while (!q.isEmpty()) {
      int i = q.pollFirst();
      dist[fa[i]] = Math.max(dist[fa[i]], dist[i] + 1);
      if (--indeg[fa[i]] == 0) {
        q.offer(fa[i]);
      }
    }
    for (int i = 0; i < n; ++i) {
      if (i == fa[fa[i]]) {
        ans += dist[i];
      }
    }
    return ans;
  }
}

class Solution {
public:
  int maximumInvitations(vector<int>& favorite) {
    return max(maxCycle(favorite), topologicalSort(favorite));
  }

  int maxCycle(vector<int>& fa) {
    int n = fa.size();
    vector<bool> vis(n);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      if (vis[i]) continue;
      vector<int> cycle;
      int j = i;
      while (!vis[j]) {
        cycle.push_back(j);
        vis[j] = true;
        j = fa[j];
      }
      for (int k = 0; k < cycle.size(); ++k) {
        if (cycle[k] == j) {
          ans = max(ans, (int) cycle.size() - k);
          break;
        }
      }
    }
    return ans;
  }

  int topologicalSort(vector<int>& fa) {
    int n = fa.size();
    vector<int> indeg(n);
    vector<int> dist(n, 1);
    for (int v : fa) ++indeg[v];
    queue<int> q;
    for (int i = 0; i < n; ++i)
      if (indeg[i] == 0) q.push(i);
    while (!q.empty()) {
      int i = q.front();
      q.pop();
      dist[fa[i]] = max(dist[fa[i]], dist[i] + 1);
      if (--indeg[fa[i]] == 0) q.push(fa[i]);
    }
    int ans = 0;
    for (int i = 0; i < n; ++i)
      if (i == fa[fa[i]]) ans += dist[i];
    return ans;
  }
};

func maximumInvitations(favorite []int) int {
  a, b := maxCycle(favorite), topologicalSort(favorite)
  return max(a, b)
}

func maxCycle(fa []int) int {
  n := len(fa)
  vis := make([]bool, n)
  ans := 0
  for i := range fa {
    if vis[i] {
      continue
    }
    j := i
    cycle := []int{}
    for !vis[j] {
      cycle = append(cycle, j)
      vis[j] = true
      j = fa[j]
    }
    for k, v := range cycle {
      if v == j {
        ans = max(ans, len(cycle)-k)
        break
      }
    }
  }
  return ans
}

func topologicalSort(fa []int) int {
  n := len(fa)
  indeg := make([]int, n)
  dist := make([]int, n)
  for i := range fa {
    dist[i] = 1
  }
  for _, v := range fa {
    indeg[v]++
  }
  q := []int{}
  for i, v := range indeg {
    if v == 0 {
      q = append(q, i)
    }
  }
  for len(q) > 0 {
    i := q[0]
    q = q[1:]
    dist[fa[i]] = max(dist[fa[i]], dist[i]+1)
    indeg[fa[i]]--
    if indeg[fa[i]] == 0 {
      q = append(q, fa[i])
    }
  }
  ans := 0
  for i := range fa {
    if i == fa[fa[i]] {
      ans += dist[i]
    }
  }
  return ans
}

function maximumInvitations(favorite: number[]): number {
  return Math.max(maxCycle(favorite), topologicalSort(favorite));
}

function maxCycle(fa: number[]): number {
  const n = fa.length;
  const vis: boolean[] = Array(n).fill(false);
  let ans = 0;
  for (let i = 0; i < n; ++i) {
    if (vis[i]) {
      continue;
    }
    const cycle: number[] = [];
    let j = i;
    for (; !vis[j]; j = fa[j]) {
      cycle.push(j);
      vis[j] = true;
    }
    for (let k = 0; k < cycle.length; ++k) {
      if (cycle[k] === j) {
        ans = Math.max(ans, cycle.length - k);
      }
    }
  }
  return ans;
}

function topologicalSort(fa: number[]): number {
  const n = fa.length;
  const indeg: number[] = Array(n).fill(0);
  const dist: number[] = Array(n).fill(1);
  for (const v of fa) {
    ++indeg[v];
  }
  const q: number[] = [];
  for (let i = 0; i < n; ++i) {
    if (indeg[i] === 0) {
      q.push(i);
    }
  }
  let ans = 0;
  while (q.length) {
    const i = q.pop()!;
    dist[fa[i]] = Math.max(dist[fa[i]], dist[i] + 1);
    if (--indeg[fa[i]] === 0) {
      q.push(fa[i]);
    }
  }
  for (let i = 0; i < n; ++i) {
    if (i === fa[fa[i]]) {
      ans += dist[i];
    }
  }
  return ans;
}