网站建设会遇到哪些问题,wordpress浏览数插件,什么是主页,win2003搭建wordpress文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时空频度】九【代码实现】十【提交结果】 一【题目类别】
图
二【题目难度】
中等
三【题目编号】
802.找到最终的安全状态
四【题目描述】
有一个有… 文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时空频度】九【代码实现】十【提交结果】 一【题目类别】
图
二【题目难度】
中等
三【题目编号】
802.找到最终的安全状态
四【题目描述】
有一个有 n 个节点的有向图节点按 0 到 n - 1 编号。图由一个 索引从 0 开始 的 2D 整数数组 graph表示 graph[i]是与节点 i 相邻的节点的整数数组这意味着从节点 i 到 graph[i]中的每个节点都有一条边。如果一个节点没有连出的有向边则该节点是 终端节点 。如果从该节点开始的所有可能路径都通向 终端节点 则该节点为 安全节点 。返回一个由图中所有 安全节点 组成的数组作为答案。答案数组中的元素应当按 升序 排列。
五【题目示例】 示例 1 输入graph [[1,2],[2,3],[5],[0],[5],[],[]]输出[2,4,5,6]解释示意图如上。 节点 5 和节点 6 是终端节点因为它们都没有出边。从节点 2、4、5 和 6 开始的所有路径都指向节点 5 或 6 。 示例 2 输入graph [[1,2,3,4],[1,2],[3,4],[0,4],[]]输出[4]解释: 只有节点 4 是终端节点从节点 4 开始的所有路径都通向节点 4 。
六【题目提示】 n g r a p h . l e n g t h n graph.length ngraph.length 1 n 1 0 4 1 n 10^4 1n104 0 g r a p h [ i ] . l e n g t h n 0 graph[i].length n 0graph[i].lengthn 0 g r a p h [ i ] [ j ] n − 1 0 graph[i][j] n - 1 0graph[i][j]n−1 g r a p h [ i ] graph[i] graph[i] 按严格递增顺序排列。图中可能包含自环。图中边的数目在范围 [ 1 , 4 ∗ 1 0 4 ] [1, 4 * 10^4] [1,4∗104] 内。
七【解题思路】
利用拓扑排序的思想解决该问题我们首先构建一个反向图即假如之前i - j那么反向图就变为j - i反向图的目的是用来后续计算出度来找到终端节点同时构建原图的出度数组后续就会用该数组来找到安全节点然后将得到的所有终端节点都入队列后续操作该队列即可得到所有终端节点然后将得到的安全节点所有终端节点都是安全节点保存到集合中然后通过逆向拓扑排序计算得到安全节点 首先从队列中取出一个安全节点然后查看它的邻接节点 然后将邻接节点的出度减1如果此时出度为0那么说明其为安全节点将其入队列和集合中 具体细节可以参考下面的代码最后返回结果即可
八【时空频度】
时间复杂度 O ( m n ) O(m n) O(mn) m m m为图的节点数 n n n为图的边数空间复杂度 O ( m n ) O(m n) O(mn) m m m为图的节点数 n n n为图的边数
九【代码实现】
Java语言版
class Solution {public ListInteger eventualSafeNodes(int[][] graph) {// 图中节点的个数int n graph.length;// 用来存储反向图ListListInteger reverseGraph new ArrayList();for (int i 0; i n; i) {reverseGraph.add(new ArrayList());}// 每个节点的出度int[] outDegree new int[n];// 构建反向图和出度数组for (int i 0; i n; i) {outDegree[i] graph[i].length;for (int neighbor : graph[i]) {reverseGraph.get(neighbor).add(i);}}// 初始化队列将所有终端节点出度为0的节点加入队列QueueInteger queue new LinkedList();for (int i 0; i n; i) {if (outDegree[i] 0) {queue.offer(i);}}// 用集合存储安全节点SetInteger safeNodes new HashSet(queue);// 逆向拓扑排序while (!queue.isEmpty()) {int node queue.poll();for (int neighbor : reverseGraph.get(node)) {outDegree[neighbor]--;if (outDegree[neighbor] 0) {safeNodes.add(neighbor);queue.offer(neighbor);}}}// 返回安全节点的升序列表ListInteger res new ArrayList(safeNodes);Collections.sort(res);return res;}
}Python语言版
class Solution:def eventualSafeNodes(self, graph: List[List[int]]) - List[int]:# 图中节点的个数n len(graph)# 用来存储反向图reverse_graph defaultdict(list)# 每个节点的出度out_degree [0] * n# 构建反向图和出度数组for i, neighboors in enumerate(graph):out_degree[i] len(neighboors)for neighboor in neighboors:reverse_graph[neighboor].append(i)# 初始化队列将所有终端节点出度为0的节点加入队列queue deque(i for i in range(n) if out_degree[i] 0)# 用集合存储安全节点safe_nodes set(queue)# 逆向拓扑排序while queue:node queue.popleft()for neighboor in reverse_graph[node]:out_degree[neighboor] - 1if out_degree[neighboor] 0:safe_nodes.add(neighboor)queue.append(neighboor)# 返回安全节点的升序列表return sorted(safe_nodes)C语言版
class Solution {
public:vectorint eventualSafeNodes(vectorvectorint graph) {// 图中节点的个数int n graph.size();// 用来存储反向图vectorvectorint reverseGraph(n);// 每个节点的出度vectorint outDegree(n, 0);// 构建反向图和出度数组for (int i 0; i n; i) {outDegree[i] graph[i].size();for (int neighbor : graph[i]) {reverseGraph[neighbor].push_back(i);}}// 初始化队列将所有终端节点出度为0的节点加入队列queueint q;// 用集合存储安全节点unordered_setint safeNodes;for (int i 0; i n; i) {if (outDegree[i] 0) {q.push(i);safeNodes.insert(i);}}// 逆向拓扑排序while (!q.empty()) {int node q.front();q.pop();for (int neighbor : reverseGraph[node]) {outDegree[neighbor]--;if (outDegree[neighbor] 0) {safeNodes.insert(neighbor);q.push(neighbor);}}}// 返回安全节点的升序列表vectorint res(safeNodes.begin(), safeNodes.end());sort(res.begin(), res.end());return res;}
};十【提交结果】 Java语言版 Python语言版 C语言版
