本文主要是介绍题目 1452: 网络寻路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述:
X 国的一个网络使用若干条线路连接若干个节点。节点间的通信是双向的。某重要数据包，为了安全起见，必须恰好被转发两次到达目的地。该包可能在任意一个节点产生，我们需要知道该网络中一共有多少种不同的转发路径。
源地址和目标地址可以相同，但中间节点必须不同。
如下图所示的网络。
1 -> 2 -> 3 -> 1 是允许的
1 -> 2 -> 1 -> 2 或者 1 -> 2 -> 3 -> 2 都是非法的。
代码:
package lanqiao;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;public class Main {static boolean vis[] = new boolean[10010]; //记录走过的节点static ArrayList<ArrayList<Integer>> map = new ArrayList<ArrayList<Integer>>(); //邻接表static int ans = 0;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();for(int i = 0;i <= n;i ++) //初始化节点，将下标为0的节点置为-1{map.add(new ArrayList<Integer>());map.get(i).add(-1);}for(int i = 1;i <= m;i ++){int u = sc.nextInt();int v = sc.nextInt();map.get(u).add(v);map.get(v).add(u);}Arrays.fill(vis,false); //初始化vis数组for(int i = 1;i <= n;i ++){vis[i] = true;dfs(i,1,i);vis[i] = false;}System.out.println(ans);}static void dfs(int cur,int step,int root) { //cur：当前节点，step：节点数，root:第一个节点if (step == 3) { //当节点数正好为3时for (int i = 1; i < map.get(cur).size(); i++) {if (!vis[map.get(cur).get(i)] || map.get(cur).get(i) == root) { //判断第四个节点是否为第一个节点或者是没有走过的节点ans++;}}} else {for (int i = 1; i < map.get(cur).size(); i++) {if (!vis[map.get(cur).get(i)]) {vis[map.get(cur).get(i)] = true;dfs(map.get(cur).get(i), step + 1, root);vis[map.get(cur).get(i)] = false;}}}}
}这篇关于题目 1452: 网络寻路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
