java实现风险度量
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
资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 2000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。
所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
java选手注意:不要使用package语句。不要使用jdk1.7及以上版本的特性。
java选手注意:主类的名字必须是:Main,否则按无效代码处理。
c/c++选手注意: main函数需要返回0
c/c++选手注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
c/c++选手注意: 所有依赖的函数必须明确地在源文件中 #include , 不能通过工程设置而省略常用头文件。
提交程序时,注意选择所期望的语言类型和编译器类型。
下面代码使用暴力求解两点之间的割点,对于数据量较大情况会超时,以下代码仅供参考。
import java.util.Scanner;
public class Main {
public static int count = 0;
public void dfs(int[][] map, boolean[] visited, int start) {
visited[start] = true;
for(int i = 1;i < map.length;i++) {
if(map[start][i] == 1 && visited[i] == false)
dfs(map, visited, i);
}
}
public void getResult(int[][] map, int start, int end) {
boolean[] visited = new boolean[map.length];
for(int i = 0;i < visited.length;i++)
visited[i] = false;
dfs(map, visited, start);
if(visited[end] == false) {
System.out.println("-1");
return;
}
for(int i = 1;i < map.length;i++) {
if(i == start || i == end)
continue;
for(int j = 0;j < visited.length;j++)
visited[j] = false;
visited[i] = true;
dfs(map, visited, start);
if(visited[end] == false)
count++;
}
System.out.println(count);
return;
}
public static void main(String[] args) {
Main test = new Main();
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[][] map = new int[n + 1][n + 1];
int m = in.nextInt();
for(int i = 1;i <= m;i++) {
int a = in.nextInt();
int b = in.nextInt();
map[a][b] = 1;
map[b][a] = 1;
}
int start = in.nextInt();
int end = in.nextInt();
test.getResult(map, start, end);
}
}
最新文章
- Android开发-mac上使用三星S3做真机调试
- JAVA 设计模式 适配器模式
- github实践操作
- Android核心分析之十六Android电话系统-概述篇
- Spring boot 1.3.5 RELEASE 官方文档中文翻译--目录
- Django生产环境的部署-Apache-mod_wsgi
- C#中删除字符串最后一个字符的几种方法
- 构建混合应用方式之 - Azure混合连接
- Flask Markup 上下文,request
- LFYZ-OJ ID: 1024 火车站
- CSS 图像高级 Css Sprites
- [JXOI2018]游戏
- 如何使用Cygwin在Windows上运行OpenSSH SSHD服务器
- 51 NOd 1459 迷宫游戏 (最短路径)
- Vue使用Typescript开发编译时提示“ERROR in ./src/main.ts Module build failed: TypeError: Cannot read property &#39;afterCompile&#39; of undefined”的解决方法
- EBS R12视图打不到数据
- lame音频编码注意的点
- 【校招面试 之 C/C++】第25题 C++ 智能指针(一)之 auto_ptr
- jQuery操纵cookie(原生javascript处理cookie)
- XtraBackup出现 Can&#39;t connect to local MySQL server through socket &#39;/var/run/mysqld/mysqld.sock&#39;
热门文章
- C# 数据操作系列 - 5. EF Core 入门
- java.sql.SQLException: The server time zone value &#39;&#214;&#208;&#185;&#250;&#177;&#234;&#215;&#188;&#202;&#177;&#188;&#228;&#39; is unrecognized的报错问题
- vue学习-第三个DEMO(计算属性和监视) v-model基础用法
- spark机器学习从0到1特征抽取–Word2Vec(十四)
- 适配器模式C++实现
- fastDFS多线程并发执行出现的问题
- php IE中文乱码
- ImportError: /lib64/libstdc++.so.6: version `CXXABI_1.3.9&#39; not found
- Java连接MySql报错—— com.mysql.cj.exceptions.InvalidConnectionAttributeException
- Robot Framework(5)- 使用测试库