Today’s problem

https://leetcode.com/problems/maximum-employees-to-be-invited-to-a-meeting/description/

Intuition

Here we have a directed graph with a ring. To get the ring, we can use topological sort. That is, to find the point which has index 0, and delete the point and its corresponding point.

By doing so, the remaining points in the graph are all in a ring.

In this problem, there are two ways to put everyone in a seat:

  1. a ring where everyone has its favorite person on his left hand site.
  2. when two person are each other’s favorite person, they themselves can form a complete ring while people who like them can form a list that points to them. Such structure is special because everyone can find his favorite person without forming a complete ring. Therefore, there could be multiple structures in the room.

Approach

  1. Use topological sort to find all the rings in the graph.
  2. Find all the special case when two people are each others’ favorite.
  3. Return the max size of a ring or return the max size of that multiple structures.

Complexity

  • Time complexity: $O(N)$

  • Space complexity: $O(N)$

Code

class Solution:
    def maximumInvitations(self, favorite: List[int]) -> int:
        N = len(favorite)
        du = [0] * N
        l = [1] * N
        for x in favorite:
            du[x] += 1

        q = deque([])
        for i in range(N):
            if du[i] == 0:
                q.append((i, 1))
        
        while(len(q) > 0):
            x, leng = q.popleft()
            to = favorite[x]
            du[to] -= 1
            l[to] = max(l[to], leng + 1)
            if du[to] == 0:
                q.append((to, leng + 1))
        
        vis = [0] * N

        def dfs(i):
            to = favorite[i]
            vis[i] = 2
            if vis[to] == 2:
                return 1
            return dfs(to) + 1

        ans = 0
        res = 0
        for i in range(N):
            if du[i] != 0 and vis[i] == 0:
                tmp = dfs(i)
                # print(i, tmp)
                if tmp == 2:
                    # print(i, favorite[i], l[i], l[favorite[i]])
                    res += l[i] + l[favorite[i]]

                else:
                    ans = max(ans, tmp)
        
        return max(ans, res)