参加会议的最多员工数

2127. 参加会议的最多员工数

一个公司准备组织一场会议，邀请名单上有 n 位员工。公司准备了一张圆形的桌子，可以坐下 任意数目 的员工。

员工编号为 0 到 n - 1 。每位员工都有一位喜欢的员工，每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工不会是他自己。

给你一个下标从 0 开始的整数数组 favorite ，其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目 。

示例 1：

输入：favorite = [2,2,1,2]
输出：3
解释：
上图展示了公司邀请员工 0，1 和 2 参加会议以及他们在圆桌上的座位。
没办法邀请所有员工参与会议，因为员工 2 没办法同时坐在 0，1 和 3 员工的旁边。
注意，公司也可以邀请员工 1，2 和 3 参加会议。
所以最多参加会议的员工数目为 3 。

示例 2：

输入：favorite = [1,2,0]
输出：3
解释：
每个员工都至少是另一个员工喜欢的员工。所以公司邀请他们所有人参加会议的前提是所有人都参加了会议。
座位安排同图 1 所示：
- 员工 0 坐在员工 2 和 1 之间。
- 员工 1 坐在员工 0 和 2 之间。
- 员工 2 坐在员工 1 和 0 之间。
参与会议的最多员工数目为 3 。

示例 3：

输入：favorite = [3,0,1,4,1]
输出：4
解释：
上图展示了公司可以邀请员工 0，1，3 和 4 参加会议以及他们在圆桌上的座位。
员工 2 无法参加，因为他喜欢的员工 0 旁边的座位已经被占领了。
所以公司只能不邀请员工 2 。
参加会议的最多员工数目为 4 。

提示：

n == favorite.length
2 <= n <= 10⁵
0 <= favorite[i] <= n - 1
favorite[i] != i

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int maximumInvitations(vector<int>& favorite) { } };

rust 解法, 执行用时: 44 ms, 内存消耗: 14.1 MB, 提交时间: 2023-11-01 00:17:57

use std::collections::VecDeque;

impl Solution {
    pub fn maximum_invitations(favorite: Vec<i32>) -> i32 {
        let n = favorite.len();
        let mut deg = vec![0; n];
        for &f in &favorite {
            deg[f as usize] += 1; // 统计基环树每个节点的入度
        }

        let mut rg = vec![vec![]; n]; // 反图
        let mut q = VecDeque::new();
        for (i, &d) in deg.iter().enumerate() {
            if d == 0 {
                q.push_back(i);
            }
        }
        while let Some(x) = q.pop_front() { // 拓扑排序，剪掉图上所有树枝
            let y = favorite[x] as usize; // x 只有一条出边
            rg[y].push(x);
            deg[y] -= 1;
            if deg[y] == 0 {
                q.push_back(y);
            }
        }

        // 通过反图 rg 寻找树枝上最深的链
        fn rdfs(x: usize, rg: &Vec<Vec<usize>>) -> i32 {
            let mut max_depth = 1;
            for &son in &rg[x] {
                max_depth = max_depth.max(rdfs(son, rg) + 1);
            }
            max_depth
        }

        let mut max_ring_size = 0;
        let mut sum_chain_size = 0;
        for i in 0..n {
            if deg[i] == 0 {
                continue;
            }

            // 遍历基环上的点
            deg[i] = 0; // 将基环上的点的入度标记为 0，避免重复访问
            let mut ring_size = 1; // 基环长度
            let mut x = favorite[i] as usize;
            while x != i {
                deg[x] = 0; // 将基环上的点的入度标记为 0，避免重复访问
                ring_size += 1;
                x = favorite[x] as usize;
            }

            if ring_size == 2 { // 基环长度为 2
                sum_chain_size += rdfs(i, &rg) + rdfs(favorite[i] as usize, &rg); // 累加两条最长链的长度
            } else {
                max_ring_size = max_ring_size.max(ring_size); // 取所有基环长度的最大值
            }
        }
        max_ring_size.max(sum_chain_size)
    }
}

javascript 解法, 执行用时: 604 ms, 内存消耗: 108 MB, 提交时间: 2023-11-01 00:17:33

/**
 * @param {number[]} favorite
 * @return {number}
 */
var maximumInvitations = function (favorite) {
    const n = favorite.length;
    const deg = Array(n).fill(0);
    for (const f of favorite) {
        deg[f]++; // 统计基环树每个节点的入度
    }

    const rg = Array(n).fill(null).map(() => []); // 反图
    const q = new Queue();
    for (let i = 0; i < n; i++) {
        if (deg[i] === 0) {
            q.enqueue(i);
        }
    }
    while (!q.isEmpty()) { // 拓扑排序，剪掉图上所有树枝
        const x = q.dequeue();
        const y = favorite[x]; // x 只有一条出边
        rg[y].push(x);
        if (--deg[y] === 0) {
            q.enqueue(y);
        }
    }

    // 通过反图 rg 寻找树枝上最深的链
    function rdfs(x) {
        let maxDepth = 1;
        for (const son of rg[x]) {
            maxDepth = Math.max(maxDepth, rdfs(son) + 1);
        }
        return maxDepth;
    }

    let maxRingSize = 0, sumChainSize = 0;
    for (let i = 0; i < n; i++) {
        if (deg[i] === 0) continue;

        // 遍历基环上的点
        deg[i] = 0; // 将基环上的点的入度标记为 0，避免重复访问
        let ringSize = 1; // 基环长度
        for (let x = favorite[i]; x !== i; x = favorite[x]) {
            deg[x] = 0; // 将基环上的点的入度标记为 0，避免重复访问
            ringSize++;
        }

        if (ringSize === 2) { // 基环长度为 2
            sumChainSize += rdfs(i) + rdfs(favorite[i]); // 累加两条最长链的长度
        } else {
            maxRingSize = Math.max(maxRingSize, ringSize); // 取所有基环长度的最大值
        }
    }
    return Math.max(maxRingSize, sumChainSize);
};

golang 解法, 执行用时: 108 ms, 内存消耗: 10.1 MB, 提交时间: 2023-09-14 10:08:24

func maximumInvitations(g []int) int { // favorite 就是内向基环森林 g
	n := len(g)
	deg := make([]int, n) // g 上每个节点的入度
	for _, w := range g {
		deg[w]++
	}

	maxDepth := make([]int, n)
	q := []int{}
	for i, d := range deg {
		if d == 0 {
			q = append(q, i)
		}
	}
	for len(q) > 0 { // 拓扑排序，剪掉 g 上的所有树枝
		v := q[0]
		q = q[1:]
		maxDepth[v]++
		w := g[v] // v 只有一条出边
		maxDepth[w] = max(maxDepth[w], maxDepth[v])
		if deg[w]--; deg[w] == 0 {
			q = append(q, w)
		}
	}

	maxRingSize, sumChainSize := 0, 0
	for i, d := range deg {
		if d == 0 {
			continue
		}
		// 遍历基环上的点（拓扑排序后入度大于 0）
		deg[i] = 0
		ringSize := 1
		for v := g[i]; v != i; v = g[v] {
			deg[v] = 0 // 将基环上的点的入度标记为 0，避免重复访问
			ringSize++
		}
		if ringSize == 2 { // 基环大小为 2
			sumChainSize += maxDepth[i] + maxDepth[g[i]] + 2 // 累加两条最长链的长度
		} else {
			maxRingSize = max(maxRingSize, ringSize) // 取所有基环的最大值
		}
	}
	return max(maxRingSize, sumChainSize)
}

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

cpp 解法, 执行用时: 192 ms, 内存消耗: 81.2 MB, 提交时间: 2023-09-14 10:08:11

class Solution {
public:
    int maximumInvitations(vector<int> &g) { // favorite 就是内向基环森林 g
        int n = g.size();
        int deg[n]; memset(deg, 0, sizeof(deg)); // g 上每个节点的入度
        for (int w: g) ++deg[w];

        int max_depth[n]; memset(max_depth, 0, sizeof(max_depth));
        queue<int> q;
        for (int i = 0; i < n; ++i)
            if (deg[i] == 0) q.emplace(i);
        while (!q.empty()) {  // 拓扑排序，剪掉 g 上的所有树枝
            int v = q.front();
            q.pop();
            ++max_depth[v];
            int w = g[v]; // v 只有一条出边
            max_depth[w] = max(max_depth[w], max_depth[v]);
            if (--deg[w] == 0) q.emplace(w);
        }

        int max_ring_size = 0, sum_chain_size = 0;
        for (int i = 0; i < n; ++i) {
            if (deg[i] == 0) continue;
            // 遍历基环上的点（拓扑排序后入度大于 0）
            deg[i] = 0;
            int ring_size = 1;
            for (int v = g[i]; v != i; v = g[v]) {
                deg[v] = 0; // 将基环上的点的入度标记为 0，避免重复访问
                ++ring_size;
            }
            if (ring_size == 2) sum_chain_size += max_depth[i] + max_depth[g[i]] + 2; // 基环大小为 2，累加两条最长链的长度
            else max_ring_size = max(max_ring_size, ring_size); // 取所有基环的最大值
        }
        return max(max_ring_size, sum_chain_size);
    }
};

java 解法, 执行用时: 15 ms, 内存消耗: 54.8 MB, 提交时间: 2023-09-14 10:07:58

class Solution {
    public int maximumInvitations(int[] g) { // favorite 就是内向基环森林 g
        var n = g.length;
        var deg = new int[n]; // g 上每个节点的入度
        for (var w : g) ++deg[w];

        var maxDepth = new int[n];
        var q = new ArrayDeque<Integer>();
        for (var i = 0; i < n; ++i)
            if (deg[i] == 0) q.push(i);
        while (!q.isEmpty()) {  // 拓扑排序，剪掉 g 上的所有树枝
            var v = q.pop();
            ++maxDepth[v];
            var w = g[v]; // v 只有一条出边
            maxDepth[w] = Math.max(maxDepth[w], maxDepth[v]);
            if (--deg[w] == 0) q.push(w);
        }

        int maxRingSize = 0, sumChainSize = 0;
        for (var i = 0; i < n; ++i) {
            if (deg[i] <= 0) continue;
            // 遍历基环上的点（拓扑排序后入度大于 0）
            deg[i] = -1;
            var ringSize = 1;
            for (var v = g[i]; v != i; v = g[v]) {
                deg[v] = -1; // 将基环上的点的入度标记为 -1，避免重复访问
                ++ringSize;
            }
            if (ringSize == 2) sumChainSize += maxDepth[i] + maxDepth[g[i]] + 2; // 基环大小为 2，累加两条最长链的长度
            else maxRingSize = Math.max(maxRingSize, ringSize); // 取所有基环的最大值
        }
        return Math.max(maxRingSize, sumChainSize);
    }
}

python3 解法, 执行用时: 316 ms, 内存消耗: 29.2 MB, 提交时间: 2023-09-14 10:07:35

class Solution:
    def maximumInvitations(self, g: List[int]) -> int:  # favorite 就是内向基环森林 g
        n = len(g)
        deg = [0] * n  # g 上每个节点的入度
        for w in g:
            deg[w] += 1

        max_depth = [0] * n
        q = deque(i for i, d in enumerate(deg) if d == 0)
        while q:  # 拓扑排序，剪掉 g 上的所有树枝
            v = q.popleft()
            max_depth[v] += 1
            w = g[v]  # v 只有一条出边
            max_depth[w] = max(max_depth[w], max_depth[v])
            deg[w] -= 1
            if deg[w] == 0:
                q.append(w)

        max_ring_size = sum_chain_size = 0
        for i, d in enumerate(deg):
            if d == 0:
                continue
            # 遍历基环上的点（拓扑排序后入度大于 0）
            deg[i] = 0
            ring_size = 1
            v = g[i]
            while v != i:
                deg[v] = 0  # 将基环上的点的入度标记为 0，避免重复访问
                ring_size += 1
                v = g[v]
            if ring_size == 2:  # 基环大小为 2
                sum_chain_size += max_depth[i] + max_depth[g[i]] + 2  # 累加两条最长链的长度
            else:
                max_ring_size = max(max_ring_size, ring_size)  # 取所有基环的最大值
        return max(max_ring_size, sum_chain_size)

上一题

下一题

详情