首页 > 代码库 > dfs 无向图两节点间的所有路径
dfs 无向图两节点间的所有路径
标题:风险度量
X星系的的防卫体系包含 n 个空间站。这 n 个空间站间有 m 条通信链路,构成通信网。
两个空间站间可能直接通信,也可能通过其它空间站中转。
对于两个站点x和y (x != y), 如果能找到一个站点z,使得:
当z被破坏后,x和y无法通信,则称z为关于x,y的关键站点。
显然,对于给定的两个站点,关于它们的关键点的个数越多,通信风险越大。
你的任务是:已知网络结构,求两站点之间的通信风险度,即:它们之间的关键点的个数。
输入数据第一行包含2个整数n(2 <= n <= 1000), m(0 <= m <= 2000),分别代表站点数,链路数。
空间站的编号从1到n。通信链路用其两端的站点编号表示。
接下来m行,每行两个整数 u,v (1 <= u, v <= n; u != v)代表一条链路。
最后1行,两个数u,v,代表被询问通信风险度的两个站点。
输出:一个整数,如果询问的两点不连通则输出-1.
例如:
用户输入:
7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6
则程序应该输出:
2
仔细看这道题,其实就是求两个节点间的所有路径,然后判断哪个节点是必不可少的。
示例中的路径有两条
1->3->4->5->6
1->3->5->6
看出3和5节点都是必不可少的,去掉3或者5后1->6无法联通。
那么用dfs求出所有路径,然后判断有多少节点出现次数跟起始节点一样多就可以了。
dfs思路大概是从起点开始搜索邻接矩阵中能访问的节点,若到达终点或者没有下一个节点可以访问就返回
1 import java.util.ArrayList; 2 import java.util.Scanner; 3 import java.util.Stack; 4 5 public class t3 { 6 7 static int[][] graph; 8 static int[] visit; 9 static Stack<Integer> res = new Stack<Integer>(); 10 static ArrayList<Integer[]> temp = new ArrayList<Integer[]>(); 11 12 public static void main(String[] args) { 13 // TODO Auto-generated method stub 14 Scanner scanner = new Scanner(System.in); 15 int n = scanner.nextInt(); 16 int m = scanner.nextInt(); 17 visit = new int[n]; 18 graph = new int[n][n]; 19 for (int i = 0; i < m; i++) { 20 int t1 = scanner.nextInt(); 21 int t2 = scanner.nextInt(); 22 graph[t1 - 1][t2 - 1] = 1; 23 graph[t2 - 1][t1 - 1] = 1; 24 } 25 int q1 = scanner.nextInt(); 26 int q2 = scanner.nextInt(); 27 dfs(q1 - 1, q2 - 1); 28 int[] z = new int[n + 1]; 29 for (int i = 0; i < temp.size(); i++) { 30 Integer[] t = temp.get(i); 31 for (int j = 0; j < t.length; j++) { 32 z[t[j]]++; //统计出现次数 33 } 34 } 35 int fin = 0; 36 for (int i = 0; i < z.length; i++) { 37 if (z[i] == z[q1] && i != q1 && i != q2) { 38 fin++; 39 } 40 } 41 System.out.println(fin); 42 } 43 44 public static void dfs(int n, int m) { 45 res.push(n); // 当前节点入栈 46 visit[n] = 1; // 设置访问位为1 47 while (true) { 48 if (n == m) { // 如果已经访问完毕,则输出 49 Integer[] t = new Integer[res.size()]; 50 for (int i = 0; i < res.size(); i++) { 51 t[i] = res.get(i) + 1; 52 } 53 temp.add(t); 54 res.pop(); // 弹出顶层 55 visit[n] = 0; // 设置未访问 56 break; 57 } 58 for (int i = 0; i < graph.length; i++) { 59 if (graph[n][i] == 1) { 60 if (visit[i] == 0) { 61 dfs(i, m); 62 } 63 } 64 } 65 res.pop(); // 到这里说明到了边界,弹出当前位置 66 visit[n] = 0; // 访问位重置 67 break; 68 } 69 } 70 71 }
dfs 无向图两节点间的所有路径
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。