Try   HackMD

LeetCode 2127. Maximum Employees to Be Invited to a Meeting

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

題目大意

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

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

思考

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

我們以 example 1 為例:

favorite = [2,2,1,2]

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

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

怎麼說呢?因為我們有

n 個頂點,以及
n
條邊,所以圖中必定含有 cycle
例如上圖中
v1
v2
形成長度為
2
的 cycle

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

我們先換個例子來看:

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

我們會注意到,圖中最長的那個 cycle

C:v1v2v3v1
會能讓最多人入座圓桌

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

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

長度最長的 cycle 就是

C:v1v2v1
v0
v3
也跟
v2
相鄰,我們還能再挑人入圓桌

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

考慮的方法其實也是想辦法抓最長的那條 chain 裡的成員進來
例如

v0v2v1 (
v3v2v1
也行) 這條 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
}