网络中删了就断联的关键路径 1192. Critical Connections in a Network
2021/9/7 6:07:38
本文主要是介绍网络中删了就断联的关键路径 1192. Critical Connections in a Network,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
There are n
servers numbered from 0
to n - 1
connected by undirected server-to-server connections
forming a network where connections[i] = [ai, bi]
represents a connection between servers ai
and bi
. Any server can reach other servers directly or indirectly through the network.
A critical connection is a connection that, if removed, will make some servers unable to reach some other server.
Return all critical connections in the network in any order.
Example 1:
Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]] Output: [[1,3]] Explanation: [[3,1]] is also accepted.
Example 2:
Input: n = 2, connections = [[0,1]] Output: [[0,1]]
有没有回路都可以有关键路径
Tarjan算法:时间戳判断-有没有回路,这只是一个辅助工具。结果大小用于判断是否这个节点唯一的neighbor就是parent
//https://leetcode.com/problems/critical-connections-in-a-network/discuss/399827/Java-DFS-Solution-similar-to-Tarjan-maybe-easier-to-understand class Solution { int T = 1; public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) { // use a timestamp, for each node, check the samllest timestamp that can reach from the node // construct the graph first List[] graph = new ArrayList[n]; for (int i = 0; i < n; i++) { graph[i] = new ArrayList<Integer>(); } for (List<Integer> conn : connections) { graph[conn.get(0)].add(conn.get(1)); graph[conn.get(1)].add(conn.get(0)); } int[] timestamp = new int[n]; // an array to save the timestamp that we meet a certain node // for each node, we need to run dfs for it, and return the smallest timestamp in all its children except its parent List<List<Integer>> criticalConns = new ArrayList<>(); dfs(n, graph, timestamp, 0, -1, criticalConns); return criticalConns; } // return the minimum timestamp it ever visited in all the neighbors private int dfs(int n, List[] graph, int[] timestamp, int i, int parent, List<List<Integer>> criticalConns) { if (timestamp[i] != 0) return timestamp[i]; timestamp[i] = T++; int minTimestamp = Integer.MAX_VALUE; for (int neighbor : (List<Integer>) graph[i]) { if (neighbor == parent) continue; // no need to check the parent //关键路径:一删掉就断联的路径 //3这个节点唯一的neighbor就是parent1,所以会continue掉。 //后面会反常,所以输出。 int neighborTimestamp = dfs(n, graph, timestamp, neighbor, i, criticalConns); //除了parent节点外,所有邻居节点中的最小值。 //因为是一路过来的,所以理应比现在的timestamp[i]更小 minTimestamp = Math.min(minTimestamp, neighborTimestamp); } if (minTimestamp >= timestamp[i]) { System.out.println("此时添加"); System.out.println("minTimestamp = " + minTimestamp); System.out.println("timestamp[i] = " + timestamp[i]); System.out.println("parent = " + parent); System.out.println("i = " + i); System.out.println(" "); if (parent >= 0) criticalConns.add(Arrays.asList(parent, i)); } return Math.min(timestamp[i], minTimestamp); } } //
4
[[0,1],[1,2],[2,0],[1,3]]
此时添加
minTimestamp = 2147483647
timestamp[i] = 4
parent = 1
i = 3
此时添加
minTimestamp = 1
timestamp[i] = 1
parent = -1
i = 0
这篇关于网络中删了就断联的关键路径 1192. Critical Connections in a Network的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain
- 2024-06-19EntBot.ai: AI Website Chatbot for Product Guides and Development Doc
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置