Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/05/19 01:36)推噓1(1推 0噓 2→)

留言3則, 3人參與討論串320/719 (看更多)

https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/description/ 1557. Minimum Number of Vertices to Reach All Nodes 找出最小的集合數量，需要滿足從每個集合的其中一個點出發，走過每個集合後可以到達所有的節點。 Example 1: https://assets.leetcode.com/uploads/2020/07/07/untitled22.png

Input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]] Output: [0,3] Explanation: It's not possible to reach all the nodes from a single vertex. From 0 we can reach [0,1,2,5]. From 3 we can reach [3,4,2,5]. So we output [0,3]. Example 2: https://assets.leetcode.com/uploads/2020/07/07/untitled.png

Input: n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]] Output: [0,2,3] Explanation: Notice that vertices 0, 3 and 2 are not reachable from any other node, so we must include them. Also any of these vertices can reach nodes 1 and 4. 思路： 1.建立無向圖 2.用dfs + 併查集把每個節點分組 3.把每個節點的root都放進Set 4.返回Set裡面的編號 Java Code： ---------------------------------------------- class Solution { public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) { int[] root = new int[n]; List<List<Integer>> graph = new ArrayList<>(); for (int i = 0; i < n; i++) { root[i] = i; graph.add(new ArrayList<>()); } for (List<Integer> edge : edges) { graph.get(edge.get(0)).add(edge.get(1)); } boolean[] visited = new boolean[n]; for (int i = 0; i < n; i++) { dfs(graph, visited, root, i); } Set<Integer> set = new HashSet<>(); for (int x : root) { set.add(find(root, x)); } return new ArrayList<>(set); } private void dfs(List<List<Integer>> graph, boolean[] visited, int[] root, int i) { if (visited[i]) { return; } visited[i] = true; for (int next : graph.get(i)) { root[next] = find(root, i); dfs(graph, visited, root, next); } } private int find(int[] root, int x) { return root[x] == x ? x : (root[x] = find(root, root[x])); } } ---------------------------------------------- 只贏過7.4% 我去漬鯊 -- https://i.imgur.com/sjdGOE3.jpg