LeetCode/go/maximum-employees-to-be-invited-to-a-meeting.go

package main

import (
	aq "github.com/emirpasic/gods/v2/queues/arrayqueue"
)

func maximumInvitations(favorite []int) int {
	n := len(favorite)

	inDegrees := make([]int, n)
	for _, fav := range favorite {
		inDegrees[fav]++
	}

	q := aq.New[int]()
	for p, favored := range inDegrees {
		if favored == 0 {
			q.Enqueue(p)
		}
	}

	depth := make([]int, n)
	for i, _ := range depth {
		depth[i] = 1
	}

	for person, ok := q.Dequeue(); ok; person, ok = q.Dequeue() {
		next := favorite[person]
		depth[next] = max(depth[next], depth[person]+1)

		inDegrees[next]--
		if inDegrees[next] == 0 {
			q.Enqueue(next)
		}
	}

	longestLoop := 0
	doubleLoop := 0

	for p0, degree := range inDegrees {
		if degree == 0 {
			continue
		}

		loopLength := 0
		for p := p0; inDegrees[p] != 0; p = favorite[p] {
			inDegrees[p] = 0
			loopLength++
		}

		if loopLength == 2 {
			doubleLoop += depth[p0] + depth[favorite[p0]]
		} else {
			longestLoop = max(longestLoop, loopLength)
		}
	}

	return max(longestLoop, doubleLoop)
}