当前位置:网站首页>LeetCode 1557. The minimum number of points that can reach all points
LeetCode 1557. The minimum number of points that can reach all points
2022-07-06 16:43:00 【Daylight629】
1557. The minimum number of points that can reach all points
To give you one Directed acyclic graph , n
Node number is 0
To n-1
, And an array of edges edges
, among edges[i] = [fromi, toi]
Represents a slave point fromi
point-to-point toi
The directed side of .
Find the smallest set of points so that all points in the graph can be reached from these points . The problem guarantees that the solution exists and is unique .
You can return these node numbers in any order .
Example 1:
Input :n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
Output :[0,3]
explain : All nodes cannot be reached from a single node . from 0 We can get to [0,1,2,5] . from 3 We can get to [3,4,2,5] . So we output [0,3] .
Example 2:
Input :n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]
Output :[0,2,3]
explain : Note the node 0,3 and 2 Unable to reach... From other nodes , So we have to include them in the result point set , These points can reach the node 1 and 4 .
Tips :
2 <= n <= 10^5
1 <= edges.length <= min(10^5, n * (n - 1) / 2)
edges[i].length == 2
0 <= fromi, toi < n
- All point pairs
(fromi, toi)
Different from each other .
Two 、 Method 1
Looking for penetration 0 The node of is
class Solution {
public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
List<Integer> res = new ArrayList<>();
Set<Integer> set = new HashSet<>();
for (List<Integer> edge : edges) {
set.add(edge.get(1));
}
for (int i = 0; i < n; i++) {
if (!set.contains(i)) {
res.add(i);
}
}
return res;
}
}
Complexity analysis
Time complexity :O(m+n), among m Is the number of edges in the graph ,n Is the number of nodes in the graph . You need to traverse all the edges to get nodes with non-zero penetration , Then traverse all nodes and keep the nodes with zero penetration .
Spatial complexity :O(n), among n Is the number of nodes in the graph . You need to use a collection to store nodes with non-zero penetration , The number of nodes in the collection will not exceed n.
边栏推荐
- Research Report on hearing health care equipment industry - market status analysis and development prospect prediction
- Codeforces Round #803 (Div. 2)A~C
- Ffmpeg command line use
- Codeforces Round #801 (Div. 2)A~C
- Educational Codeforces Round 122 (Rated for Div. 2)
- Specify the format time, and fill in zero before the month and days
- 业务系统兼容数据库Oracle/PostgreSQL(openGauss)/MySQL的琐事
- 解决Intel12代酷睿CPU【小核载满,大核围观】的问题(WIN11)
- Hbuilder x format shortcut key settings
- Research Report of desktop clinical chemical analyzer industry - market status analysis and development prospect prediction
猜你喜欢
Click QT button to switch qlineedit focus (including code)
Story of [Kun Jintong]: talk about Chinese character coding and common character sets
第5章 NameNode和SecondaryNameNode
300th weekly match - leetcode
Chapter 5 detailed explanation of consumer groups
Spark independent cluster dynamic online and offline worker node
Oneforall installation and use
Mp4 format details
(lightoj - 1323) billiard balls (thinking)
顺丰科技智慧物流校园技术挑战赛(无t4)
随机推荐
Soft music -js find the number of times that character appears in the string - Feng Hao's blog
【锟斤拷】的故事:谈谈汉字编码和常用字符集
Research Report on hearing health care equipment industry - market status analysis and development prospect prediction
(lightoj - 1370) Bi shoe and phi shoe (Euler function tabulation)
Bisphenol based CE Resin Industry Research Report - market status analysis and development prospect forecast
业务系统兼容数据库Oracle/PostgreSQL(openGauss)/MySQL的琐事
SQL quick start
Research Report on market supply and demand and strategy of Chinese table lamp industry
(lightoj - 1369) answering queries (thinking)
(lightoj - 1354) IP checking (Analog)
How to insert mathematical formulas in CSDN blog
力扣leetcode第 280 场周赛
Installation and configuration of MariaDB
Problem - 922D、Robot Vacuum Cleaner - Codeforces
Solve the problem that intel12 generation core CPU single thread only runs on small cores
JS encapsulates the method of array inversion -- Feng Hao's blog
Chapter 1 overview of MapReduce
第2章 HFDS的Shell操作
Chapter 2 shell operation of hfds
Research Report on market supply and demand and strategy of China's tetraacetylethylenediamine (TAED) industry