【LeetCode每日一题】——802.找到最终的安全状态
一【标题类别】[*]图
二【标题难度】
[*]中等
三【标题编号】
[*]802.找到最终的安全状态
四【标题描述】
[*]有一个有 n 个节点的有向图，节点按 0 到 n - 1 编号。图由一个 索引从 0 开始 的 2D 整数数组 graph体现， graph是与节点 i 相邻的节点的整数数组，这意味着从节点 i 到 graph中的每个节点都有一条边。
[*]如果一个节点没有连出的有向边，则该节点是 终端节点 。如果从该节点开始的全部可能路径都通向 终端节点 ，则该节点为 安全节点 。
[*]返回一个由图中全部 安全节点 组成的数组作为答案。答案数组中的元素应当按 升序 分列。
五【标题示例】
[*] 示例 1：
https://i-blog.csdnimg.cn/direct/cb6d43b9a90248d9b09051d139c8ceea.png#pic_center
[*]输入：graph = [,,,,,[],[]]
[*]输出：
[*]表明：示意图如上。
[*]节点 5 和节点 6 是终端节点，因为它们都没有出边。
[*]从节点 2、4、5 和 6 开始的全部路径都指向节点 5 或 6 。
[*] 示例 2：
[*]输入：graph = [,,,,[]]
[*]输出：
[*]表明:
[*]只有节点 4 是终端节点，从节点 4 开始的全部路径都通向节点 4 。
六【标题提示】
[*] n = = g r a p h . l e n g t h n == graph.length n==graph.length
[*] 1 < = n < = 1 0 4 1 <= n <= 10^4 1<=n<=104
[*] 0 < = g r a p h [ i ] . l e n g t h < = n 0 <= graph.length <= n 0<=graph.length<=n
[*] 0 < = g r a p h [ i ] [ j ] < = n − 1 0 <= graph <= n - 1 0<=graph<=n−1
[*] g r a p h [ i ] graph graph 按严酷递增次序分列。
[*]图中可能包含自环。
[*]图中边的数目在范围 [ 1 , 4 ∗ 1 0 4 ] 内。
七【解题思路】
[*]利用拓扑排序的思想解决该问题
[*]我们起首构建一个反向图，即如果之前i -> j，那么反向图就变为j -> i，反向图的目的是用来后续盘算出度来找到终端节点
[*]同时构建原图的出度数组，后续就会用该数组来找到安全节点
[*]然后将得到的全部终端节点都入队列，后续操作该队列即可得到全部终端节点
[*]然后将得到的安全节点（全部终端节点都是安全节点）生存到聚会合
[*]然后通过逆向拓扑排序盘算得到安全节点：
[*]起首从队列中取出一个安全节点
[*]然后检察它的邻接节点
[*]然后将邻接节点的出度减1
[*]如果此时出度为0，那么阐明其为安全节点，将其入队列和聚会合
[*]具体细节可以参考下面的代码
[*]最后返回结果即可
八【时空频度】
[*]时间复杂度： O ( m + n ) O(m + n) O(m+n)， m m m为图的节点数， n n n为图的边数
[*]空间复杂度： O ( m + n ) O(m + n) O(m+n)， m m m为图的节点数， n n n为图的边数
九【代码实现】
[*]Java语言版
class Solution {
public List<Integer> eventualSafeNodes(int[][] graph) {
// 图中节点的个数
int n = graph.length;
// 用来存储反向图
List<List<Integer>> reverseGraph = new ArrayList<>();
for (int i = 0; i < n; i++) {
reverseGraph.add(new ArrayList<>());
}
// 每个节点的出度
int[] outDegree = new int;
// 构建反向图和出度数组
for (int i = 0; i < n; i++) {
outDegree = graph.length;
for (int neighbor : graph) {
reverseGraph.get(neighbor).add(i);
}
}
// 初始化队列，将所有终端节点（出度为0的节点）加入队列
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (outDegree == 0) {
queue.offer(i);
}
}
// 用集合存储安全节点
Set<Integer> safeNodes = new HashSet<>(queue);
// 逆向拓扑排序
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : reverseGraph.get(node)) {
outDegree--;
if (outDegree == 0) {
safeNodes.add(neighbor);
queue.offer(neighbor);
}
}
}
// 返回安全节点的升序列表
List<Integer> res = new ArrayList<>(safeNodes);
Collections.sort(res);
return res;
}
}
[*]Python语言版
class Solution:
def eventualSafeNodes(self, graph: List]) -> List:
# 图中节点的个数
n = len(graph)
# 用来存储反向图
reverse_graph = defaultdict(list)
# 每个节点的出度
out_degree = * n
# 构建反向图和出度数组
for i, neighboors in enumerate(graph):
out_degree = len(neighboors)
for neighboor in neighboors:
reverse_graph.append(i)
# 初始化队列，将所有终端节点（出度为0的节点）加入队列
queue = deque(i for i in range(n) if out_degree == 0)
# 用集合存储安全节点
safe_nodes = set(queue)
# 逆向拓扑排序
while queue:
node = queue.popleft()
for neighboor in reverse_graph:
out_degree -= 1
if out_degree == 0:
safe_nodes.add(neighboor)
queue.append(neighboor)
# 返回安全节点的升序列表
return sorted(safe_nodes)
[*]C++语言版
class Solution {
public:
vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
// 图中节点的个数
int n = graph.size();
// 用来存储反向图
vector<vector<int>> reverseGraph(n);
// 每个节点的出度
vector<int> outDegree(n, 0);
// 构建反向图和出度数组
for (int i = 0; i < n; i++) {
outDegree = graph.size();
for (int neighbor : graph) {
reverseGraph.push_back(i);
}
}
// 初始化队列，将所有终端节点（出度为0的节点）加入队列
queue<int> q;
// 用集合存储安全节点
unordered_set<int> safeNodes;
for (int i = 0; i < n; i++) {
if (outDegree == 0) {
q.push(i);
safeNodes.insert(i);
}
}
// 逆向拓扑排序
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neighbor : reverseGraph) {
outDegree--;
if (outDegree == 0) {
safeNodes.insert(neighbor);
q.push(neighbor);
}
}
}
// 返回安全节点的升序列表
vector<int> res(safeNodes.begin(), safeNodes.end());
sort(res.begin(), res.end());
return res;
}
};
十【提交结果】
[*] Java语言版
https://i-blog.csdnimg.cn/direct/0c153bcdff34455889374cfbca1a0039.png#pic_center
[*] Python语言版
https://i-blog.csdnimg.cn/direct/6ebae24c5b564d1693b0f7bb0de51808.png#pic_center
[*] C++语言版
https://i-blog.csdnimg.cn/direct/c058fdce872a4e3bb869c6d5e7656aec.png#pic_center
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]