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

(Updated: )
(9 mins to read)

题意

有n个人，每个人有另外一个喜欢的人，现在有一个圆桌，要求座位上的每个人都和他喜欢的人相邻，问座位上最多能有几个人。

做法

每个节点都有一条出边，构成若干棵内向基环树。

现在考虑每棵基环树，显然可以让环上的所有人都坐下。

但是从样例1就可以看出一种特殊的case，如果环的大小为2，此时是可以继续加人的。设环上的两个点为x和y，那么可以再塞进x子树内的最长链以及y子树内的最长链，而且可以继续把其它大小为2的环以及对应的链拼接进来。

因此这道题只需要找出每棵基环树的环的大小，如果大于2，取max；否则再找出这两个点各自子树内的最长链，取sum。最后两种情况再去max即可。

做的时候看到样例就意识到环的大小为2是个特殊点，但是没想到可以拼接，而且也没确定每个联通块都是基环树这一点，所以写的很乱（完全在瞎写），也WA了好几次。。😭我一开始以为大小为2的环最多只能多带1个人，为了判断这个环还有其他点，我从一个非环上的点开始爬，最后再处理纯环（如果知道每个连通块都是基环树这一点，完全没必要分成两块代码写）。后来发现结论不对之后，这个代码框架其实不太好，但也懒得改了，所以调试起来也很烦，手画了好几个错的样例。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class Solution {
public:
    int maximumInvitations(vector<int>& favorite) {
        int n = favorite.size();
        int ans = 0, ans2 = 0;
        vector<int> cnt(n), vis(n);
        vector<vector<int>> G(n);
        for (int i = 0; i < favorite.size(); i++) {
            cnt[favorite[i]]++;
            G[i].push_back(favorite[i]);
            G[favorite[i]].push_back(i);
        }
        vector<int> tmp(n);
        function<int(int, int)> get = [&](int u, int u2) {
            int d = 1;
            tmp[u] = 1;
            for (int v : G[u]) {
                if (v != u2 && !tmp[v]) {
                    d = max(d, get(v, u2) + 1);
                }
            }
            return d;
        };
        int two = 0;
        for (int i = 0; i < n; i++) {
            if (!cnt[i]) {
                vector<int> loop;
                int j = i;
                for (int j = i; ; j = favorite[j]) {
                    loop.push_back(j);
                    if (!vis[j]) {
                        vis[j] = 1;
                    } else if (vis[j] == 1) {
                        int sz = loop.size();
                        for (int i = 0; i < sz; i++) {
                            if (i > 0) cnt[loop[i]]--;
                            vis[loop[i]] = 2;
                            if (j == loop[i] && i != sz - 1) {
                                int x = i, y = sz - x - 1;
                                if (y == 2) {
                                    int cur = get(j, loop[i + 1]) + get(loop[i + 1], j);
                                    ans2 = max(ans2, cur);
                                    two += cur;
                                } else {
                                    ans = max(ans, y);
                                }
                            }
                        }
                        break;
                    } else if (vis[j] == 2) {
                        int sz = loop.size();
                        for (int i = 1; i < sz; i++) {
                            cnt[loop[i]]--;
                        }
                        break;
                    }
                }
            }
        }
        memset(vis.data(), 0, n << 2);
        for (int i = 0; i < n; i++) {
            while (cnt[i]) {
                vector<int> loop;
                int j = i;
                for (int j = i; ; j = favorite[j]) {
                    loop.push_back(j);
                    if (!vis[j]) {
                        vis[j] = 1;
                    } else {
                        int sz = loop.size();
                        if (sz == 3) {
                            two += 2;
                            ans2 = max(ans2, 2);
                        } else {
                            ans = max(ans, sz - 1);
                        }
                        for (int i = 0; i < sz; i++) {
                            vis[loop[i]] = 0;
                            if (i > 0) cnt[loop[i]]--;
                        }
                        break;
                    }
                }
            }
        }
        ans = max(ans, two);
        return ans;
    }
};

基环树找环可以把所有非环上的边用拓扑排序去掉。

下面代码的rg包含了所有非环边，而环边用favorite数组就可以拿到。此外，其实可以直接在拓扑排序的时候算出最长链，也就不需要建rg了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    int maximumInvitations(vector<int> &favorite) {
        int n = favorite.size();
        vector<int> deg(n);
        for (int f: favorite) {
            deg[f]++; // 统计基环树每个节点的入度
        }

        vector<vector<int>> rg(n); // 反图
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (deg[i] == 0) {
                q.push(i);
            }
        }
        while (!q.empty()) { // 拓扑排序，剪掉图上所有树枝
            int x = q.front();
            q.pop();
            int y = favorite[x]; // x 只有一条出边
            rg[y].push_back(x);
            if (--deg[y] == 0) {
                q.push(y);
            }
        }

        // 通过反图 rg 寻找树枝上最深的链
        function<int(int)> rdfs = [&](int x) -> int {
            int max_depth = 1;
            for (int son: rg[x]) {
                max_depth = max(max_depth, rdfs(son) + 1);
            }
            return max_depth;
        };

        int max_ring_size = 0, sum_chain_size = 0;
        for (int i = 0; i < n; i++) {
            if (deg[i] == 0) continue;

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

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