@ninijia 在 Leetcode每日一题练习 ------ 2127. 参加会议的最多员工数 中发帖
从Leetcode 每日一题练习继续讨论:
2127. 参加会议的最多员工数
2127. Maximum Employees to Be Invited to a Meeting
题解
本题是一道难题,本题有一个很重要的条件即每个人只能喜欢一个人,平时在说到三角恋时常常喜欢用一个图来表示A喜欢B,B喜欢C,C喜欢A,用有向箭头表示每个人喜欢的方向,得到的就是一个三角形仅有三个节点的有向图,那么本题也可以做同样的处理构建出一个有向图。
接下来就要考虑这个有向图的特点了,该图任意节点的入度不受限制但出度必定为1。如果我们要让尽可能多的人同时坐在圆桌上,就要找到一条有向图中的路径,这个路径要么自身就是一个环,这样环内的所有人都可以在满足题目条件的情况下坐在同一个圆桌上(类似三角恋,只不过人数更多,从环上任意一点开始最终会回到该点),要么只有一个二元环,即存在一个A喜欢B,B喜欢A的小环,...