【图论】有向无环图中一个节点的所有祖先 - 邻接表(DFS)

文章目录

  • 题目:有向无环图中一个节点的所有祖先
    • 题目描述
    • 代码与解题思路

题目:有向无环图中一个节点的所有祖先

2192. 有向无环图中一个节点的所有祖先

题目描述

代码与解题思路

func getAncestors(n int, edges [][]int) [][]int {
    g := make([][]int, n)
    for _, e := range edges {
        x, y := e[0], e[1]
        g[x] = append(g[x], y)
    }
    ans := make([][]int, n)
    vis := make([]int, n)
    start := 0
    var dfs func(int)
    dfs = func(x int) {
        vis[x] = start+1 // 因为 vis 初始是 0, 所以要 +1 错开
        for _, v := range g[x] {
            if vis[v] != start+1 {
                ans[v] = append(ans[v], start)
                dfs(v)
            }
        }
    }
    for start < n {
        dfs(start)
        start++
    }
    return ans
}

采用思路:灵神的题解

这道题的核心就在于如何解决重复遍历的问题,用什么方法都做

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/515577.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C#清空窗体的背景图片

目录 一、涉及到的知识点 1.设置窗体的背景图 2.加载窗体背景图 3.清空窗体的背景图 二、 示例 一、涉及到的知识点 1.设置窗体的背景图 详见本文作者的其他文章&#xff1a;C#手动改变自制窗体的大小-CSDN博客 https://wenchm.blog.csdn.net/article/details/137027140…

链路追踪原理

分布式系统为什么需要链路追踪&#xff1f; 随着互联网业务快速扩展&#xff0c;软件架构也日益变得复杂&#xff0c;为了适应海量用户高并发请求&#xff0c;系统中越来越多的组件开始走向分布式化&#xff0c;如单体架构拆分为微服务、服务内缓存变为分布式缓存、服务组件通…

IDEA2023.1.1中文插件

1.启动IDEA 选中Customize 2.选择All settings 3.选中Plugins,再搜索栏里输入Chinese,找到 "Chinese (Simplified) Language"插件&#xff0c;点击 Install 进行安装。 4. 安装完成后&#xff0c;重启IntelliJ IDEA&#xff0c;即可看到界面语言已经变为中文。

HashMap为啥线程不安全?

1. HashMap1.7在多线程并发下扩容时&#xff0c;头插法会出现环。 /*** Rehashes the contents of this map into a new array with a* larger capacity. This method is called automatically when the* number of keys in this map reaches its threshold.** If current cap…

回溯算法|491.递增子序列

力扣题目链接 class Solution { private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex) {if (path.size() > 1) {result.push_back(path);// 注意这里不要加return&#xff0c;要取树上…

[计算机知识] TCP/IP网络模型、MySQL的结构

TCP/IP网络模型 应用层 给用户提供应用功能&#xff0c;如HTTP, DNS 应用层处于用户态&#xff0c;传输层及以下处于内核态 传输层 给应用层提供网络支持&#xff0c;如TCP, UDP TCP提供稳定、面向连接的网络传输协议 应用层的数据可能会太大&#xff0c;就需要进行拆分…

【GAMES101】Lecture08 09 Shading 3 (Texture Mapping cont.) 纹理映射 续集

目录 0 引言1 如何在三角形内进行插值&#xff1a;重心坐标1.1 为什么要在三角形内插值1.2 重心坐标1.3 使用重心坐标做三角形内颜色插值 2 应用纹理2.1 简单的纹理映射&#xff1a;漫反射2.2 问题&#xff1a;纹理放大&#xff08;采用插值解决&#xff09;2.2 点查询和范围查…

Qt主窗口 之:停靠/悬浮窗口(QDockWidget)

一、QDockWidget概述 QDockWidget 是 Qt 中的一个窗口部件&#xff0c;用于创建可停靠的窗口&#xff0c;通常用于构建多文档接口&#xff08;MDI&#xff09;或可定制的用户界面。QDockWidget 允许用户将窗口停靠在应用程序的主窗口周围&#xff0c;或将其拖动到独立的浮动窗…

STM32

GPIO通用输入输出口 GPIO:8种输入输出模式 浮空输入可读取引脚电平&#xff0c;若引脚悬空&#xff0c;电平不确定上拉输入可读取引脚电平&#xff0c;内部接上拉电阻&#xff0c;悬空时默认为高电平下拉输入可读取引脚电平&#xff0c;内部接下拉电阻&#xff0c;悬空时默认…

视频编辑的瑞士军刀,MoviePy库的详解与应用示例

左手编程&#xff0c;右手年华。大家好&#xff0c;我是一点&#xff0c;关注我&#xff0c;带你走入编程的世界。 公众号&#xff1a;一点sir&#xff0c;关注领取python编程资料 在数字媒体的时代&#xff0c;视频内容的创作和编辑变得越来越重要。无论是社交媒体上的短视频&…

【数据结构】初识数据结构与复杂度总结

前言 C语言这块算是总结完了&#xff0c;那从本篇开始就是步入一个新的大章——数据结构&#xff0c;这篇我们先来认识一下数据结构有关知识&#xff0c;以及复杂度的相关知识 个人主页&#xff1a;小张同学zkf 若有问题 评论区见 感兴趣就关注一下吧 目录 1.什么是数据结构 2.…

原创【matcap材质在ue4中的实现办法】

matcap材质在ue4中的实现办法 2023-08-29 15:34 https://www.bilibili.com/video/BV1GR4y1b76n/?spm_id_from333.337.search-card.all.click&vd_sourced76b773892c830a157c0ccc97ba78411 评论(0)

PS从入门到精通视频各类教程整理全集,包含素材、作业等(8)复发

PS从入门到精通视频各类教程整理全集&#xff0c;包含素材、作业等 最新PS以及插件合集&#xff0c;可在我以往文章中找到 由于阿里云盘有分享次受限制和文件大小限制&#xff0c;今天先分享到这里&#xff0c;后续持续更新 B站-PS异闻录&#xff1a;萌新系统入门课课程视频 …

Golang学习系列1-pprof性能调优

1. pprof 简述 一位亦师亦友的话让我记忆犹新&#xff0c;他说“学习一个新事务&#xff0c;应该从三个方面入手what,why,how;且三者的重要程度应该是递减”。所以在本文的第一部分先叙述下pprof的what & why。 1.1 What&#xff1f; pprof是golang自身提供的一种性能分…

基于顺序表的学生成绩管理系统

&#x1f308; 个人主页&#xff1a;白子寰 &#x1f525; 分类专栏&#xff1a;python从入门到精通&#xff0c;魔法指针&#xff0c;进阶C&#xff0c;C语言&#xff0c;C语言题集&#xff0c;C语言实现游戏&#x1f448; 希望得到您的订阅和支持~ &#x1f4a1; 坚持创作博文…

【Flink技术原理构造及特性】

1、Flink简介 Flink是一个批处理和流处理结合的统一计算框架&#xff0c;其核心是一个提供了数据分发以及并行化计算的流数据处理引擎。它的最大亮点是流处理&#xff0c;是业界最顶级的开源流处理引擎。 Flink最适合的应用场景是低时延的数据处理&#xff08;Data Processin…

算法练习—day1

title: 算法练习—day1 date: 2024-04-03 21:49:55 tags: 算法 categories:LeetCode typora-root-url: 算法练习—day1 网址&#xff1a;https://red568.github.io 704. 二分查找 题目&#xff1a; 题目分析&#xff1a; 左右指针分别为[left,right]&#xff0c;每次都取中…

练习 19 Web [BJDCTF2020]Easy MD5

如果你是第一批做这个题的&#xff0c;这道题一点也不easy 打开在前端代码里面看到&#xff0c;输入框输入的内容实际是’password’ 随意输入内容&#xff0c;查看响应header中的内容有一句SQL代码&#xff0c;可知我们要让password在md5后返回值为true 然后尬住&#xff…

区间DP模型

目录 环形石子合并思路代码实现 能量项链代码实现 加分二叉树思路代码实现 凸多边形的划分代码实现 棋盘分割题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 佬的题解代码实现 环形石子合并 题目描述&#xff1a; 将 n n n 堆石子绕圆形操场排放&#xff0c;现要将…

前端(动态雪景背景+动态蝴蝶)

1.CSS样式 <style>html, body, a, div, span, table, tr, td, strong, ul, ol, li, h1, h2, h3, p, input {font-weight: inherit;font-size: inherit;list-style: none;border-spacing: 0;border: 0;border-collapse: collapse;text-decoration: none;padding: 0;margi…