1557.可以到达所有点的最少点数目

2024-04-24 04:20
文章标签 最少 所有 数目 到达 1557

本文主要是介绍1557.可以到达所有点的最少点数目,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

给你一个 有向无环图n 个节点编号为 0n-1 ,以及一个边数组 edges ,其中 edges[i] = [fromi, toi] 表示一条从点 fromi 到点 toi 的有向边。

找到最小的点集使得从这些点出发能到达图中所有点。题目保证解存在且唯一。

你可以以任意顺序返回这些节点编号。

示例 1:

img

输入:n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
输出:[0,3]
解释:从单个节点出发无法到达所有节点。从 0 出发我们可以到达 [0,1,2,5] 。从 3 出发我们可以到达 [3,4,2,5] 。所以我们输出 [0,3] 。

示例 2:

img

输入:n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]
输出:[0,2,3]
解释:注意到节点 0,3 和 2 无法从其他节点到达,所以我们必须将它们包含在结果点集中,这些点都能到达节点 1 和 4 。

思路

出入度统计

首先,观察示例可以发现答案最小集有两个规律:

  • 答案必须包括入度为0的节点,如果没有包括,那么该节点肯定不能到达;

  • 如果有一条a->b的边,那么b一定不会在答案当中,因为选a能到达b也能到达a

由于保证解存在且唯一,所以最小集即为图中所有入度为0的节点

python代码:

class Solution(object):def findSmallestSetOfVertices(self, n, edges):ans = []inDegree = [0 for _ in range(n)]for i,j in edges:inDegree[j] += 1for i in range(n):if inDegree[i] == 0:ans.append(i)return ans

由于python set 可以用来去重,可以统计edges 所有可到达的点,即第二个元素,然后从 0-n中剔除这部分即可:

class Solution(object):def findSmallestSetOfVertices(self, n, edges):return list(set(range(n)) - set(j for i,j in edges))

这篇关于1557.可以到达所有点的最少点数目的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/930745

相关文章

hdu1496(用hash思想统计数目)

作为一个刚学hash的孩子,感觉这道题目很不错,灵活的运用的数组的下标。 解题步骤:如果用常规方法解,那么时间复杂度为O(n^4),肯定会超时,然后参考了网上的解题方法,将等式分成两个部分,a*x1^2+b*x2^2和c*x3^2+d*x4^2, 各自作为数组的下标,如果两部分相加为0,则满足等式; 代码如下: #include<iostream>#include<algorithm

Collection的所有的方法演示

import java.util.ArrayList;import java.util.Collection;import java.util.Iterator;public class TestCollection {/*** @param args* Collection的所有的方法演示* 此程序没有使用泛型,所以可以添加任意类型* 以后如果写到泛型会补充这一方面的内容*/public s

Temu官方宣导务必将所有的点位材料进行检测-RSL资质检测

关于饰品类产品合规问题宣导: 产品法规RSL要求 RSL测试是根据REACH法规及附录17的要求进行测试。REACH法规是欧洲一项重要的法规,其中包含许多对化学物质进行限制的规定和高度关注物质。 为了确保珠宝首饰的安全性,欧盟REACH法规规定,珠宝首饰上架各大电商平台前必须进行RSLReport(欧盟禁限用化学物质检测报告)资质认证,以确保产品不含对人体有害的化学物质。 RSL-铅,

获取所有classpath指定包下类的所有子类

1.问题 开发过程中,有时需要找到所有classpath下,特定包下某个类的所有子类,如何做到? 2. 实现 比较常见的解决方案是自己遍历目录,查找所有.class文件。 下面这个方法使用spring工具类实现,简化过程,不再需要自己遍历目录 /*** 获取在指定包下某个class的所有非抽象子类** @param parentClass 父类* @param packagePat

为libpng不同架构创建构建目录、编译、安装以及合并库文件的所有步骤。

好的。既然你已经有了 libpng 的源代码,并且当前处在它的目录下,我们可以简化脚本,不再需要下载和解压源代码这一步。以下是修改后的脚本:```sh#!/bin/bash# 当前目录即 libpng 源代码目录LIBPNG_SRC_DIR=$(pwd)# 设置工作目录WORK_DIR=$(pwd)/libpng_buildBUILD_DIR_X86_64="$WORK_DIR/build

Mybatis logj日志配置问题 以及日志相关的所有问题

使用Mybatis的时候,有些时候能输出(主要是指sql,参数,结果)日志。有些时候就不能。 无法输出日志的时候,无论怎么配置log4j,不管是properties的还是xml的,都不起作用。 有些时候,我们没做什么配置就能输出日志.... 这是一个让无数人烦躁的问题。其实解决问题很容易(我过了这么久才解决,以前都用拦截器输出)。 这是一个普大喜奔的日子,让我们一起来看看如何解决mybat

力扣 797. 所有可能路径【DFS】

1. 题目 2. 代码 DFS , 直接见代码 class Solution {public:vector<int> path;vector<vector<int>> res; // 结果集void dfs(vector<vector<int>>& graph, int cur, int n){// 找出所有从节点 0 到节点 n-1 的路径// 下标从 0 开始的if (

【每日一题】LeetCode 2379.得到K个黑块的最少涂色次数(字符串、滑动窗口)

【每日一题】LeetCode 2379.得到K个黑块的最少涂色次数(字符串、滑动窗口) 题目描述 给定一个字符串 blocks,其中每个字符代表一个颜色块,可以是 ‘W’(白色)或 ‘B’(黑色)。你需要找到一个至少包含 k 个连续黑色块的子串。每次操作可以将一个白色块变成黑色块。你的任务是找到至少出现一次连续 k 个黑色块的最少操作次数。 和该题目类似:【每日一题】LeetCode 202

智力题:25匹马5条跑道找最快的3匹马,最少需要跑几次?

要找出25匹马中最快的3匹马,使用5条跑道,最少需要跑几次?我们可以通过逐步推理来解决这个问题。 第一步:分组比赛 首先,我们将25匹马分成5组,每组5匹马。每组进行一次比赛,这样我们就有5次比赛的结果。 组1:A1, A2, A3, A4, A5 组2:B1, B2, B3, B4, B5 组3:C1, C2, C3, C4, C5 组4:D1, D2, D3, D4, D5 组

Linux下删除某个文件之外的其他所有文件

在windows下要删除一个文件夹下除某个文件之外的其他所有文件很简单,选择这个文件,再反选即可。Linux下可能很多人不知道如何实现这种效果,这里分享2种方法: 1 使用xargs ls | grep -v xxx | xargs rm -r 使用时将xxx替换成要保留的文件名即可。 如果有相似的文件名,可以使用正则表达式匹配完整的文件名,如: 有两个相似的文件名33和331,此时要保留