首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >LeetCode 5300. 有向无环图中一个节点的所有祖先(拓扑排序)

LeetCode 5300. 有向无环图中一个节点的所有祖先(拓扑排序)

作者头像
Michael阿明
发布于 2022-03-10 10:32:42
发布于 2022-03-10 10:32:42
98400
代码可运行
举报
运行总次数:0
代码可运行

文章目录

1. 题目

给你一个正整数 n ,它表示一个 有向无环图 中节点的数目,节点编号为 0 到 n - 1 (包括两者)。

给你一个二维整数数组 edges ,其中 edges[i] = [fromi, toi] 表示图中一条从 fromi 到 toi 的单向边

请你返回一个数组 answer,其中 answer[i]是第 i 个节点的所有 祖先 ,这些祖先节点 升序 排序。

如果 u 通过一系列边,能够到达 v ,那么我们称节点 u 是节点 v 的 祖先 节点。

示例 1:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
输出:[[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
解释:
上图为输入所对应的图。
- 节点 012 没有任何祖先。
- 节点 32 个祖先 01- 节点 42 个祖先 02- 节点 53 个祖先 013- 节点 65 个祖先 01234- 节点 74 个祖先 0123

示例 2:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
输出:[[],[0],[0,1],[0,1,2],[0,1,2,3]]
解释:
上图为输入所对应的图。
- 节点 0 没有任何祖先。
- 节点 11 个祖先 0- 节点 22 个祖先 01- 节点 33 个祖先 012- 节点 44 个祖先 0123 。
 
提示:
1 <= n <= 1000
0 <= edges.length <= min(2000, n * (n - 1) / 2)
edges[i].length == 2
0 <= fromi, toi <= n - 1
fromi != toi
图中不会有重边。
图是 有向 且 无环 的。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • 拓扑排序的思路
  • 建图,入度计数,从入度为 0 的开始遍历
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<set<int>> ancest(n);
        vector<int> indegree(n);
        vector<unordered_set<int>> g(n);
        for(auto& e : edges)
        {
            g[e[0]].insert(e[1]);//建图
            indegree[e[1]]++;//入度
        }
        queue<int> q;
        for(int i = 0; i < n; ++i)
        {
            if(indegree[i] == 0)
                q.push(i);//入度为0加入队列
        }
        while(!q.empty())
        {
            int id = q.front();
            q.pop();
            for(auto nid : g[id])
            {
                for(auto a : ancest[id])
                {
                    ancest[nid].insert(a);//继承之前节点的祖先
                }
                ancest[nid].insert(id);//加入from节点为祖先
                if(--indegree[nid] == 0)
                    q.push(nid);
            }
        }
        vector<vector<int>> ans(n);
        for(int i = 0; i < n; ++i)
        {
            ans[i] = vector<int>(ancest[i].begin(), ancest[i].end());//转化为答案
        }
        return ans;
    }
};

492 ms 140.6 MB C++


我的CSDN博客地址 https://michael.blog.csdn.net/

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
LeetCode 1786. 从第一个节点出发到最后一个节点的受限路径数(迪杰斯特拉 + 拓扑排序)
现有一个加权无向连通图。 给你一个正整数 n ,表示图中有 n 个节点,并按从 1 到 n 给节点编号;另给你一个数组 edges ,其中每个 edges[i] = [ui, vi, weighti] 表示存在一条位于节点 ui 和 vi 之间的边,这条边的权重为 weighti 。
Michael阿明
2021/09/06
5940
LeetCode 第 33 场双周赛(511/3304,前15.5%,第4次全部通过)
全国排名: 511 / 3304,15.5%;全球排名: 1626 / 11366,14.3%
Michael阿明
2021/02/19
3590
LeetCode 210. 课程表 II(拓扑排序)
在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0,1]
Michael阿明
2020/07/13
4810
【备战蓝桥杯】 算法·每日一题(详解+多解)-- day11
本文总结算法中涉及图的最短路径可能用到的算法,主要分为两大类,一类是单源最短路径,即计算一个给定的顶点到其他顶点的最短路径,一类是多源最短路径,即计算顶点两两之间的最短路径。
苏州程序大白
2022/05/13
9320
【备战蓝桥杯】 算法·每日一题(详解+多解)-- day11
LeetCode 2050. 并行课程 III(拓扑排序)
给你一个整数 n ,表示有 n 节课,课程编号从 1 到 n 。 同时给你一个二维整数数组 relations ,其中 relations[j] = [prevCoursej, nextCoursej] ,表示课程 prevCoursej 必须在课程 nextCoursej 之前 完成(先修课的关系)。 同时给你一个下标从 0 开始的整数数组 time ,其中 time[i] 表示完成第 (i+1) 门课程需要花费的 月份 数。
Michael阿明
2022/01/07
5290
LeetCode 2050. 并行课程 III(拓扑排序)
算法沉淀——拓扑排序
在下面的这张图中,1这个点的入度就是0,2这个点的入度就是2,因为有两条有向线段指向2这个点。
用户11316056
2024/10/16
1660
算法沉淀——拓扑排序
LeetCode 269. 火星词典(拓扑排序)
假设,您并不知道其中字母之间的先后顺序。 但是,会收到词典中获得一个 不为空的 单词列表。 因为是从词典中获得的,所以该单词列表内的单词已经 按这门新语言的字母顺序进行了排序。
Michael阿明
2021/02/19
1.1K0
LeetCode 207. 课程表(拓扑排序)
你这个学期必须选修 numCourse 门课程,记为 0 到 numCourse-1 。
Michael阿明
2020/07/13
5810
LeetCode 207. 课程表(拓扑排序)
LeetCode 834. 树中距离之和(树上DP)*
给定一个无向、连通的树。树中有 N 个标记为 0...N-1 的节点以及 N-1 条边 。
Michael阿明
2021/02/19
6030
LeetCode 1377. T 秒后青蛙的位置(BFS)
给你一棵由 n 个顶点组成的无向树,顶点编号从 1 到 n。青蛙从 顶点 1 开始起跳。规则如下:
Michael阿明
2020/07/13
5750
LeetCode 第 198 场周赛(434/5778,前7.51%)
第二题图的边给的不一定按顺序的,我按有序的做,错误一次,第三题好难跳过了,第四题暴力超时,贪心不对。继续加油!
Michael阿明
2021/02/19
3700
LeetCode 1136. 平行课程(拓扑排序)
给你一份课程关系表 relations[i] = [X, Y],用以表示课程 X 和课程 Y 之间的先修关系:课程 X 必须在课程 Y 之前修完。
Michael阿明
2021/02/19
7860
拓扑排序:BFS 解法的原理探究与流程梳理
入度就是当前的这个点有几条线指向当前的点 比如说我们的这个4,入度就是2,因为有3和2指向4这个点
Undoom
2025/07/24
810
拓扑排序:BFS 解法的原理探究与流程梳理
Leetcode|BFS+DFS拓扑排序|210. 课程表 II
1 BFS拓扑排序 class Solution { public: vector<vector<int>> edges; // 邻接矩阵 vector<int> indegree; // 入度表 vector<int> res; vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) { edges.resize(numCou
SL_World
2022/01/10
2510
Leetcode|BFS+DFS拓扑排序|210. 课程表 II
LeetCode 1489. 找到最小生成树里的关键边和伪关键边(并查集+kruskal最小生成树)
给你一个 n 个点的带权无向连通图,节点编号为 0 到 n-1 ,同时还有一个数组 edges ,其中 edges[i] = [fromi, toi, weighti] 表示在 fromi 和 toi 节点之间有一条带权无向边。
Michael阿明
2021/02/19
1K0
LeetCode 1489. 找到最小生成树里的关键边和伪关键边(并查集+kruskal最小生成树)
BFS:解决拓扑排序问题
要知道什么拓扑排序我们首先要知道什么是有向无环图,有向无环图我们看名字其实就很容易理解,有向就是有方向,无环就是没有环形结构,这里我们展示一下有向无环图和有向有环图:
用户11305458
2024/10/09
2480
BFS:解决拓扑排序问题
LeetCode 851. 喧闹和富有(拓扑排序)
在一组 N 个人(编号为 0, 1, 2, ..., N-1)中,每个人都有不同数目的钱,以及不同程度的安静(quietness)。
Michael阿明
2021/02/19
3010
LeetCode 1273. 删除树节点(拓扑排序/DFS)
1. 题目 给你一棵以节点 0 为根节点的树,定义如下: 节点的总数为 nodes 个; 第 i 个节点的值为 value[i] ; 第 i 个节点的父节点是 parent[i] 。 请你删除节点值之
Michael阿明
2020/07/13
5450
LeetCode 444. 序列重建(拓扑排序)
验证原始的序列 org 是否可以从序列集 seqs 中唯一地重建。 序列 org 是 1 到 n 整数的排列,其中 1 ≤ n ≤ 104。 重建是指在序列集 seqs 中构建最短的公共超序列。(即使得所有 seqs 中的序列都是该最短序列的子序列)。 确定是否只可以从 seqs 重建唯一的序列,且该序列就是 org 。
Michael阿明
2021/02/19
5940
【C++】多源BFS问题和拓扑排序
顾名思义,单源BFS是只有一个起点,博客CSDN中已经阐述过,如有不明白者,可前去一探究竟,而多源BFS是有多个起点,然后同时出发,到达终点;
啊QQQQQ
2024/11/19
1610
【C++】多源BFS问题和拓扑排序
推荐阅读
相关推荐
LeetCode 1786. 从第一个节点出发到最后一个节点的受限路径数(迪杰斯特拉 + 拓扑排序)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档