力扣周赛304 6135. 图中的最长环 内向基环树

力扣周赛304 6135. 图中的最长环 内向基环树

做题结果

周赛失败，晚上复盘一下子就写出来了T T。本来想问问大佬，然后试一下就出来了

方法：模拟

单指针的图，最后都可以形成一个或多个类似上图的形状，多个外部线连到内部环

当我们从一个指针访问到重复节点的时候，可能得到上面红色线对应的结果，红色线对应的每个点都应该判重，打标记，后续在访问到红色位置访问过的节点时，直接结束

1. 访问到重复节点：记录当前时间戳和旧时间戳的差值结束，同时记录已访问点

2. 访问到非法节点（旧节点访问过的节点）：直接结束，记录已访问点

class Solution { public int longestCycle(int[] edges) { int n = edges.length; boolean[] visited = new boolean[n]; int ans = -1; for(int i = 0; i < n; i++){ if(visited[i]) continue; Map used = new HashMap<>(); int pos = i; int size = 0; while (edges[pos]!=-1&&!used.containsKey(edges[pos])&&!visited[edges[pos]]){ ++size; pos = edges[pos]; used.put(pos,size); } if(edges[pos]!=-1&&!visited[edges[pos]]){ ans = Math.max(ans,size-used.get(edges[pos])+1); } for(Integer key:used.keySet()){ visited[key]=true; } } return ans; } }

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