受邀参加会议的最大员工数

2127。最大的员工被邀请参加会议

>

难度： hard

主题：深度优先搜索，图形，拓扑排序

>一家公司正在组织会议，并有n名员工名单，等待被邀请。他们已经安排了一张大圆桌会议，能够座位员工的任何数字。

员工的编号为0到n -1。每个员工都有一个> 的人，只有当他们才能坐在他们最喜欢的人旁边的情况下，他们才会参加会议>桌子。员工的最喜欢的人是>不是他们自己。> 给定a

0-索引

整数阵列，其中最喜欢的[i]表示ith> th 员工的最喜欢的人，返回^{>可以邀请参加会议的员工}。 >>示例1：

>输入：

fairm = [2,2,1,2]

>输出：
• 3
>说明：
• >上图显示了公司如何邀请员工0、1和2，并将其坐在圆桌会议上。
• 不能邀请所有员工邀请，因为员工2不能同时坐在员工0、1和3旁边。> 请注意，该公司还可以邀请员工1、2和3，并给他们所需的座位。
  • >可以邀请参加会议的最大员工数量为3。>
  • >
  >示例2：
>输入：

fairm = [1,2,0]

> >输出：

3

• >说明：
• 每个员工是至少一个其他员工的最喜欢的人，而公司邀请他们的唯一途径是他们邀请每位员工。 座位的安排将与示例1：中给出的图相同。 >员工0将位于员工2和1之间
>员工1将位于员工0和2之间。
• >员工2将位于员工1和0之间。
  >可以邀请参加会议的最大员工数量为3。>
  • >示例3：
  • • >输入： fairm = [3,0,1,4,1]
    • >输出：4
    • >说明：
      • 上面的图显示了公司将如何邀请员工0、1、3和4，并将其坐在圆桌会议上。
      >员工2无法邀请，因为摄取了他们最喜欢的员工1旁边的两个景点。
      • 因此，公司将他们排除在会议之外。
      >
      • 可以邀请参加会议的最大员工人数为4。>
    >约束：

    > n == fale.length

    2＆lt; = n＆lt; = 10
    • 5
    • > ^{0＆lt; = fairm [i]＆lt; = n -1} >最爱[i]！= i
    • 提示：

    >从给定的数组的喜爱中，创建一个图形，对于每个索引i，都有一个从喜欢的[i]到i的指向边缘。该图将是循环和无环边缘链的组合。现在，我们可以选择员工坐在桌子上的方式？>

    >我们可以选择员工的第一种方法是选择图表的周期。可以证明，在这种情况下，不在周期中的员工永远无法坐在桌子上（除非周期的长度为2）。
    第二种方法是结合无环链。最多可以通过长度2的循环将两个链组合在一起，其中每个链在周期中的一个员工中结束。
    2. 解决方案：
    该解决方案涉及分析由喜爱阵列形成的图表中的周期和链。

    >让我们在PHP中实现此解决方案： 2127。最大的员工被邀请参加会议

    解释：

    
    图表表示

    ：

    <?php /**
     * @param Integer[] $favorite
     * @return Integer
     */
    function maximumInvitations($favorite) {
        ...
        ...
        ...
        /**
         * go to ./solution.php
         */
    }
    
    // Example usage:
    $favorites1 = [2, 2, 1, 2];
    $favorites2 = [1, 2, 0];
    $favorites3 = [3, 0, 1, 4, 1];
    
    echo maximumInvitations($favorites1) . "\n"; // Output: 3
    echo maximumInvitations($favorites2) . "\n"; // Output: 3
    echo maximumInvitations($favorites3) . "\n"; // Output: 4
    ?>
    

    每个员工都指向他们的最爱，形成有向图。
    阵列indegree用于跟踪每个人指向多少员工。>

    1. >链条的拓扑排序
       ：
       • >没有传入边缘的员工（indegree = 0）进行处理以计算导致周期的链长。>

    2. 循环检测：

       >访问员工以检测周期。一旦找到一个周期：
       对于长度2的循环，循环每个节点附着的链被合并。
       对于更长的周期，考虑了整个周期的长度。

    3. 结果
       • ：
         所有循环长度的最大值和从2个长度循环中合并链的长度的总和。
       这种方法可确保效率的效率，其时间复杂性为
       >
    o（n）

    4. > ，使其适用于最高>

       10 5
       的大型输入。 >
       • 。
    联系链接

    如果您发现此系列有帮助，请考虑在Github上给出 reposority >在您喜欢的社交网络上分享帖子？您的支持对我来说意义重大！>

    如果您想要这样的更多有用的内容，请随时关注我：

    >

    • LinkedIn
    • github

以上是受邀参加会议的最大员工数的详细内容。更多信息请关注PHP中文网其他相关文章！