# LeetCode 2127. Maximum Employees to Be Invited to a Meeting

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

## 題目大意

有 `n` 位員工，會議室有一張圓桌可坐任意數量的人
員工編號從 `0` 到 `n-1` ，給定一個長度 `n` 的陣列 `favorite` 分別代表每位員工希望自己旁邊一定要坐哪位員工，任意員工 `i` 之 `favorite[i]` 保證不為 `i` 自己

回傳最多可讓多少員工坐在圓桌前，滿足每位員工旁邊皆坐著自己的 favorite person

## 思考

這題看似簡單，但還是需要非常細心的考慮
絕對沒有實際上看起來容易

我們以 example 1 為例：

`favorite = [2,2,1,2]`

<center><img src="https://assets.leetcode.com/uploads/2021/12/14/ex1.png" alt="leetcode 2127 example 1"></center>

如果我們把 favorite 關係看作有向邊，那麼這題就能變成在有向圖上的問題


對圖論足夠敏銳的人此刻應該要能發現，我們造出來的有向圖必定含有 cycle

怎麼說呢？因為我們有 $n$ 個頂點，以及 $n$ 條邊，所以圖中必定含有 cycle
例如上圖中 $v_1$ 跟 $v_2$ 形成長度為 $2$ 的 cycle

那知道了這件事又能怎樣呢？

<center>
<img src="https://drive.miyago9267.com/d/file/img/mygo/%E6%98%AF%E5%8F%88%E6%80%8E%E6%A8%A3.jpg" alt="是又怎樣" style="width: 60%">
</center>

我們先換個例子來看：


我們會注意到，圖中最長的那個 cycle $C: v_1\rightarrow v_2\rightarrow v_3\rightarrow v_1$
會能讓最多人入座圓桌

那麼剩下的人呢？
我們再看回 example 1


長度最長的 cycle 就是 $C: v_1\rightarrow v_2\rightarrow v_1$
但 $v_0$ 跟 $v_3$ 也跟 $v_2$ 相鄰，我們還能再挑人入圓桌

這是因為 3-cycle 以上才會形成封閉小圈圈，如果我們只是兩人互相喜歡 (`lenCycle == 2`) 那麼還需要考慮其他指過來的頂點才行

考慮的方法其實也是想辦法抓最長的那條 chain 裡的成員進來
例如 $v_0\rightarrow v_2 \rightarrow v_1$ ($v_3\rightarrow v_2 \rightarrow v_1$ 也行) 這條 chain 長度為 $3$ ，比我們只看 cycle 的長度還長

所以最終答案就是 $3$

***

根據題意，每位員工只會有一位不是自己本人的 favorite person ，換句話說就是有向圖上每點 out degree 為 $1$ 且圖上無 loop

我們想要找 chain ，關鍵就在於還有哪些人指過來到 2-cycle 上的頂點嘛，也就是說我們是要看 in degree

先初始化 `indeg` ：

for (int u = 0; u < n; ++u)
{
    ++nodes[favorite[u]].indeg;
}

接著我們先看沒人喜歡的員工 (`nodes[u].indeg == 0`) ，看看這些員工都喜歡誰
這個過程是未來需要找 chain 時，找出最長的那條 chain 用的
想法就是 2-cycle 上的頂點為終點的話，除起點外應該會有能一路從起點指過來的路徑，即為 chain

為了方便，我們初始化 `nodes[u].dist == 1` (每個點都是長度為 $1$ 的 chain)，每次我們比較 `u` 跟其喜歡的 `v` 兩者的 chain 長度： `max(nodes[v].dist, nodes[u].dist + 1)`
其中 `nodes[u].dist + 1` 代表接上 `u` 後的長度，並且跟 `v` 當前最長的長度比，每次更新
更新 `v` 的原因是因為我們期望 2-cycle 上的頂點會當作 `v` 的角色
更新之後，別忘了要標示拜訪過的點，做法就是把這個入度扣掉 (`--node[v].indeg`) ，表示 `u` 考慮過了，少掉一個射入 `v` 的頂點
如果 `v` 這般操作後也變成入度為 $0$ 的點，就要把他加入拜訪

上述準備完後，我們就可以找最長的 cycle 了，並且跟最長 chain (2-cycle 上兩點的 chain 長度相加) 做比較，取最大值即為所求

如果是 cycle 上的點，那肯定是有 cycle 上的其他頂點射向他，上述操作過後，這些點的入度必不為 $0$ ，由此我們就能找出 cycle 了

### C++ 參考解答

class Solution
{
public:
    int maximumInvitations(vector<int> &favorite)
    {
        const int n = favorite.size();
        vector<Node> nodes(n);

        for (int u = 0; u < n; ++u)
        {
            ++nodes[favorite[u]].indeg;
        }

        queue<int> q;
        for (int u = 0; u < n; ++u)
        {
            if (!nodes[u].indeg)
                q.push(u);
        }

        while (!q.empty())
        {
            const int u = q.front();
            q.pop();
            const int v = favorite[u];

            nodes[v].dist = max(nodes[v].dist, nodes[u].dist + 1);
            if (--nodes[v].indeg == 0)
                q.push(v);
        }

        int maxCycle = 0, maxChain = 0;

        for (int u = 0; u < n; ++u)
        {
            if (!nodes[u].indeg)
                continue;

            int lenCycle = 0;
            int v = u;
            while (nodes[v].indeg)
            {
                nodes[v].indeg = 0; // visited
                ++lenCycle;
                v = favorite[v];
            }

            if (lenCycle == 2)
                maxChain += nodes[u].dist + nodes[favorite[u]].dist;
            else
                maxCycle = max(maxCycle, lenCycle);
        }

        return max(maxCycle, maxChain);
    }

private:
    struct Node
    {
        int indeg, dist;
        Node() : indeg(0), dist(1) {}
    };
};

### Go 參考解答

func maximumInvitations(favorite []int) int {
	n := len(favorite)
	nodes := make([]Node, n)
	for i := 0; i < n; i++ {
		nodes[i].dist = 1
	}

	for _, u := range favorite {
		nodes[u].indeg++
	}

	q := make([]int, 0)
	for u := 0; u < n; u++ {
		if nodes[u].indeg == 0 {
			q = append(q, u)
		}
	}

	for len(q) > 0 {
		u := q[0]
		q = q[1:]
		v := favorite[u]

		nodes[v].dist = max(nodes[v].dist, nodes[u].dist+1)
		nodes[v].indeg--
		if nodes[v].indeg == 0 {
			q = append(q, v)
		}
	}

	maxCycle, maxChain := 0, 0

	for u := 0; u < n; u++ {
		if nodes[u].indeg == 0 {
			continue
		}

		lenCycle := 0
		v := u
		for nodes[v].indeg != 0 {
			nodes[v].indeg = 0 // Mark as visited
			lenCycle++
			v = favorite[v]
		}

		if lenCycle == 2 {
			maxChain += nodes[u].dist + nodes[favorite[u]].dist
		} else {
			maxCycle = max(maxCycle, lenCycle)
		}
	}

	return max(maxCycle, maxChain)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

type Node struct {
	indeg, dist int
}