力扣 2127. 参加会议的最多员工数 拓扑剪枝与2360补充

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 <= 1e5
• 0 <= favorite[i] <= n - 1
• favorite[i] != i

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

 完全忘记了，然后又看了一次答案，重写了2360

方法：分类讨论与拓扑剪枝

参考题解：内向基环树：拓扑排序 + 分类讨论（Python/Java/C++/Go）

1. 有两种情况，一种是两个人互相喜欢，后面有其他人喜欢就这堆人都可以作为环的一部分，如下图，可作为一种安排方式，可看到，如果两人成环，那就可以把每个两人成环+挂载链的合起来，作为一次会议

 2. 直接一个大于2的环，注意大于2的环不能向外挂载，比如3,4之间挂了一个5,5喜欢3，那4就放不进来了，4没有喜欢5.所以大于2的环只能独立存在

 

 

 3.实际上，环外面，会出现一些指向环但是不成环的点

这些点可以通过入度为0，逐步进行拓扑剪枝去除，双点成环情况时，再通过环上的点取反图遍历

 

class Solution {
    public int maximumInvitations(int[] favorite) {
        //1.记录反图
        int n = favorite.length;
        Set<Integer>[] reverse = new HashSet[n];
        Arrays.setAll(reverse,o->new HashSet<Integer>());
        int[] indegree = new int[n];
        for(int i = 0; i < n; i++){
            int w = favorite[i];
            reverse[w].add(i);
            indegree[w]++;
        }
        //2.减掉枝丫
        Queue<Integer> queue =new LinkedList<>();
        for(int i = 0; i < n; i++){
            if(indegree[i]==0) queue.offer(i);
        }

        while (!queue.isEmpty()){
            int v = queue.poll();
            indegree[favorite[v]]--;
            if(indegree[favorite[v]]==0) queue.offer(favorite[v]);
        }
        //3.双元素环和与单环
        int sum = 0;
        int ans = 0;
        for(int i = 0; i < n; i++){
            if(indegree[i]<=0) continue;
            int j = i;
            int size = 1;
            while (favorite[j]!=i) {
                ++size;
                j = favorite[j];
                indegree[j]=0;
            }

            if(size==2){
                reverse[i].remove(favorite[i]);
                reverse[favorite[i]].remove(i);
                sum+=dfs(reverse,i)+dfs(reverse,favorite[i])+2;
            }else{
                ans = Math.max(size,ans);
            }
        }
        return Math.max(sum,ans);
    }

    private int dfs(Set<Integer>[] reverse, int index){
        int ans = 0;
        for(Integer next:reverse[index]){
            ans = Math.max(ans,dfs(reverse,next)+1);
        }
        return ans;
    }
}

附录：使用2127的方式，对2360拓扑剪枝：

class Solution {
    public int longestCycle(int[] edges) {
        //1.记录反图
        int n = edges.length;
        Set<Integer>[] reverse = new HashSet[n];
        Arrays.setAll(reverse,o->new HashSet<Integer>());
        int[] indegree = new int[n];
        for(int i = 0; i < n; i++){
            int w = edges[i];
            if(w!=-1){
                reverse[w].add(i);
                indegree[w]++;
            }
          
        }
        //2.减掉枝丫
        Queue<Integer> queue =new LinkedList<>();
        for(int i = 0; i < n; i++){
            if(indegree[i]==0) queue.offer(i);
        }

       while (!queue.isEmpty()){
            int v = queue.poll();
            if(edges[v]!=-1) {
                indegree[edges[v]]--;
                if(indegree[edges[v]]==0) queue.offer(edges[v]);
            }
        }


        int ans = -1;
        for(int i = 0; i < n; i++){
            if(indegree[i]<=0) continue;
            int j = i;
            int size = 1;
            while (edges[j]!=i) {
                ++size;
                j = edges[j];
                indegree[j]=0;
            }

            ans = Math.max(ans,size);
        }
        return ans;
    }
}