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

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

做题结果

完全忘记了，然后又看了一次答案，重写了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[] reverse = new HashSet[n]; Arrays.setAll(reverse,o->new HashSet()); int[] indegree = new int[n]; for(int i = 0; i < n; i++){ int w = favorite[i]; reverse[w].add(i); indegree[w]++; } //2.减掉枝丫 Queue 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[] 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[] reverse = new HashSet[n]; Arrays.setAll(reverse,o->new HashSet()); 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 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; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。