题目 1452: 网络寻路

devtools/2024/12/23 7:22:08/

题目描述:

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;}}}}
}


http://www.ppmy.cn/devtools/26951.html

相关文章

小剧场短剧影视小程序源码_后端PHP

项目运行截图 源码贡献 https://githubs.xyz/boot?app42 部署说明 linux/win任选 PHP版本&#xff1a;7.3/7.2&#xff08;测试时我用的7.2要安装sg扩展 &#xff09; 批量替换域名http://video.owoii.com更换为你的 批量替换域名http://120.79.77.163:1更换为你的 这两个…

3.C++动态内存管理(超全)

目录 1 .C/C 内存分布 2. C语言中动态内存管理方式&#xff1a;malloc/calloc/realloc/free 3. C内存管理方式 3.1 new/delete操作内置类型 3.2 new和delete操作自定义类型 3.3 operator new函数 3.4 定位new表达式(placement-new) &#xff08;了解&#xff09; 4. 常…

自定义SpringBoot启动图标

在SpringBoot项目的resources目录下创建banner.txt文件 在https://www.bootschool.net/网站上复制Ascll艺术字&#xff08;图&#xff09;粘贴到banner.txt中保存。 启动项目就会加载 可以修改颜色&#xff0c;和版本号 ${application.version} 输出版本 ${spring-boot.v…

第三十章:docker如何部署openresty

docker如何部署openresty 目标 了解docker 中volumes数据卷的读写控制通过 openresty 配置掌握挂载nginx.confOpenResty OpenResty(又称ngx_openresty)是一个基于Nginx的可伸缩的Web平台,由中国人章亦春发起。它利用了Nginx模块化、可扩展的特性,开发了一系列的增强模块,…

Python 与 TensorFlow2 生成式 AI(五)

原文&#xff1a;zh.annas-archive.org/md5/d06d282ea0d9c23c57f0ce31225acf76 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 第十二章&#xff1a;用生成式人工智能玩视频游戏&#xff1a;GAIL 在之前的章节中&#xff0c;我们已经看到如何使用生成式人工智能来生成…

撞库攻击是什么,如何进行有效的防护阻止

在网络威胁领域&#xff0c;暴力破解攻击仍然是网络犯罪分子非常喜爱且有利可图的攻击方法。&#xff0c;黑客通过收集互联网已泄露的用户和密码信息&#xff0c;生成对应的字典表&#xff0c;由于许多用户重复使用相同的用户名和密码&#xff0c;攻击者可以使用撞库攻击获得对…

Postman 汉化安装及使用指南:快速上手 Postman 中文版

Postman 是一款常用的 API 测试工具&#xff0c;可以方便地进行接口测试、调试和文档编写。本文将详细介绍如何下载安装 Postman 并汉化&#xff0c;包括每个步骤的详细说明。 下载安装 Postman 1、打开浏览器&#xff0c;访问 Postman 官网&#xff0c;下载适用于自己系统的…

STM32G030F6P6TR 芯片TSSOP20 MCU单片机微控制器芯片

STM32G030F6P6TR 在物联网&#xff08;IoT&#xff09;设备中的典型应用案例包括但不限于以下几个方面&#xff1a; 1. 环境监测系统&#xff1a; 使用传感器来监测温度、湿度、气压等环境因素&#xff0c;并通过无线通信模块将数据发送到中央服务器或云端平台进行分析和监控。…