- 浏览: 36542 次
- 性别:
- 来自: 长沙
最新评论
-
qq_24665727:
厉害!
netty3.0的服务端及客户端的搭建 -
huangshanghua:
有些意思。加油
Java版飞机游戏 -
MoonMonster:
再看,发现中间有段体现自己好无知。
使用一个break跳出多重循环 -
BS_YG:
666,之前上网看socket的代码还奇怪loop是什么意思, ...
使用一个break跳出多重循环 -
BS_YG:
MoonMonster 写道BS_YG 写道涛霸可以啊,建议下 ...
Java框架集合--常见类的常用方法的常规使用
Problem Description
多多终于从小学升入了初中。新班级共有n人,学号分别为从1~n。其中多多的学号是1号。
新班级里有m对同学是事先就相互认识的,其他的同学互相都不认识。
多多新班级里所有的同学(包括多多在内)都非常害羞,如果两个同学不认识,那么必须要由一个同时认识这两名同学的人来介绍他们认识,否则他们就会一直互相不认识。
现在你已经知道了这m对相互认识的同学的信息。请你写一个程序,来计算一下多多最多可以认识多少名同学。
Input
输入的第一行包含一个数字T,代表测试数据的组数。
每组数据第一行包含两个正整数n m,代表班级的人数和已知相互认识的关系数。
以下m行每行包含两个数字x y,代表学号为x的同学和学号为y的同学相互认识。
数据保证n小于100,m小于3000,x y 均小于等于n。
Output
每组输出占用一行,仅包含一个数字,即多多最多可以认识的同学数。
Sample Input
2
5 3
1 3
2 5
3 4
10 7
1 6
2 5
2 6
3 4
4 6
6 7
8 9
Sample Output
2
6
一、第一种做法:ArrayList+Stack
这道题第一反应的办法就是图+深搜,但当初做这题时还不会用,但又不想放弃,便试着用ArrayList+Stack给折腾出来了。
以下是代码:
稍微添上图解,写了好几个月了,刚开始看的时候都没看明白...再次深深明白注释的作用。
从stack中取出栈顶元素,然后去arr中匹配,若某一组数据有跟它一样的,且另一个在person中不存在,则把数据入栈,并且放进person中,result加1;同时在arr中把那组数据remove掉;循环直到栈空。
二、第二种做法:图+深搜
在看完图那章后,就一直想用图的知识把这题给做了,但却一直拖到今天,拖延症患者啊...
没有什么可以说的,直接贴代码:
三、第三种做法:数组
可以直接用数组做出来:
1.建一个二维数组,如果认识则置为1,否则为0
2.首先将跟 1 一组的入栈
3.然后仿照深搜,计算得到结果。
因为链接失效了,所以没法判断第二种和第三种做法的代码是否能得到正确结果(题目给出的测试数据通过了),但第一种肯定是通过了的。
深知自己能力之不足,所以若有谁偶然看到这篇博文,发现错误或有待提高之处,先谢谢各位的纠正,指出。
多多终于从小学升入了初中。新班级共有n人,学号分别为从1~n。其中多多的学号是1号。
新班级里有m对同学是事先就相互认识的,其他的同学互相都不认识。
多多新班级里所有的同学(包括多多在内)都非常害羞,如果两个同学不认识,那么必须要由一个同时认识这两名同学的人来介绍他们认识,否则他们就会一直互相不认识。
现在你已经知道了这m对相互认识的同学的信息。请你写一个程序,来计算一下多多最多可以认识多少名同学。
Input
输入的第一行包含一个数字T,代表测试数据的组数。
每组数据第一行包含两个正整数n m,代表班级的人数和已知相互认识的关系数。
以下m行每行包含两个数字x y,代表学号为x的同学和学号为y的同学相互认识。
数据保证n小于100,m小于3000,x y 均小于等于n。
Output
每组输出占用一行,仅包含一个数字,即多多最多可以认识的同学数。
Sample Input
2
5 3
1 3
2 5
3 4
10 7
1 6
2 5
2 6
3 4
4 6
6 7
8 9
Sample Output
2
6
一、第一种做法:ArrayList+Stack
这道题第一反应的办法就是图+深搜,但当初做这题时还不会用,但又不想放弃,便试着用ArrayList+Stack给折腾出来了。
以下是代码:
import java.util.ArrayList; import java.util.Scanner; import java.util.Stack; /** * @author MoonMonster * @date 2015-7-10 下午03:50:54 */ public class Main { public static void main(String[] args) { int n; // 班级人数 int m; // 认识对数 int T; // 测试数 int a, b; Scanner sc = new Scanner(System.in); T = sc.nextInt(); while (true) { int result = 0; //计算结果 if (T == 0) { break; } //创建集合和对象 //arr中存储除了含有多多的之外的每一组的数据 ArrayList<Student> arr = new ArrayList(); //stack中存储与多多认识但还没有对他认识的人进行查找的数据 Stack<Integer> stack = new Stack(); //临时变量,存储从stack中remove的数据 ArrayList<Student> _arr = new ArrayList(); //存储已经入栈过的数据 ArrayList<Integer> person = new ArrayList(); //输入认识的人的对 n = sc.nextInt(); m = sc.nextInt(); //存储一组数据 Student[] st = new Student[m]; for (int i = 0; i < m; i++) { st[i] = new Student(); a = sc.nextInt(); b = sc.nextInt(); st[i].x = a; st[i].y = b; //将每一组数据加入集合 arr.add(st[i]); //遍历从1(多多)开始 if (a == 1 || b == 1) { if (a == 1) { //将多多认识的人的数据放入栈中 stack.push(b); //表示该数据已经入过栈 person.add(b); } else { stack.push(a); person.add(a); } //多多认识的人+1 result++; //将含有1的数据对移除 arr.remove(st[i]); } } //如果栈里有数据,则一直遍历 while (!stack.empty()) { //获得栈中的数据,与集合中的数据进行比较 //栈中存的都是多多认识的人 int c = (int) stack.pop(); for (int i = 0; i < arr.size(); i++) { Student _st = arr.get(i); if (c == _st.x || c == _st.y) { if (c == _st.x) { //判断要入栈的数是否已经入过栈 //将C认识的人(即多多会认识的人)入栈 if(!person.contains(_st.y)){ result++; stack.push(_st.y); //入栈 person.add(_st.y); //入栈,新加入的数据 } } else { //判断要入栈的数是否已经入过栈 if(!person.contains(_st.x)){ result++; stack.push(_st.x); person.add(_st.x); } } //表示_st的数据已经查找过 _arr.add(_st); } } for( int i=0; i<_arr.size(); i++ ){ //剔除查找了的数据 arr.remove(_arr.get(i)); } _arr.clear(); //清空数据 } if( n == 1 ){ System.out.println(0); }else{ System.out.println(result); } T --; } } } class Student { public int x; public int y; }
稍微添上图解,写了好几个月了,刚开始看的时候都没看明白...再次深深明白注释的作用。
从stack中取出栈顶元素,然后去arr中匹配,若某一组数据有跟它一样的,且另一个在person中不存在,则把数据入栈,并且放进person中,result加1;同时在arr中把那组数据remove掉;循环直到栈空。
二、第二种做法:图+深搜
在看完图那章后,就一直想用图的知识把这题给做了,但却一直拖到今天,拖延症患者啊...
没有什么可以说的,直接贴代码:
package com.ct.graph; import java.util.Scanner; import java.util.Stack; /** * @author MoonMonster * @date 2015-10-16 下午02:46:38 */ //边 class Edge{ //索引 public int index; public Edge next; } //顶点 class VexNode{ //数据 public int data; public Edge firstedge; } //邻接表 class MyGraph{ public int vexnum, arcnum; VexNode[] vexnode; public MyGraph(int n,int m){ this.vexnum = n; this.arcnum = m; vexnode = new VexNode[n]; for(int i=0; i<n; i++){ vexnode[i] = new VexNode(); } } } public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int n, m; int T; MyGraph graph = null; //测试数目 T = sc.nextInt(); while(true){ if(T == 0){ break; } T --; //总人数和组数 n = sc.nextInt(); m = sc.nextInt(); graph = new MyGraph(n,m); createGraph(graph); //print(graph); System.out.println(DFS(graph)); } } public static void createGraph(MyGraph graph){ int a, b; //初始化节点数据 for(int i=0; i<graph.vexnum; i++){ graph.vexnode[i].data = i; } for(int i=0; i<graph.arcnum; i++){ //vexnode中的数据是从0开始,所以这儿都-1 a = sc.nextInt() - 1; b = sc.nextInt() - 1; Edge edge; //连接a,b两个顶点 edge = new Edge(); edge.index = a; edge.next = graph.vexnode[b].firstedge; graph.vexnode[b].firstedge = edge; edge = new Edge(); edge.index = b; edge.next = graph.vexnode[a].firstedge; graph.vexnode[a].firstedge = edge; } } //深搜 public static int DFS(MyGraph graph){ boolean visited[] = new boolean[graph.vexnum+1]; int result = 0; Stack<Integer> stack = new Stack<Integer>(); for(int i=0; i<graph.vexnum; i++){ visited[i] = false; } stack.push(0); visited[0] = true; while(!stack.empty()){ int num = stack.pop(); Edge edge = graph.vexnode[num].firstedge; //对从栈中取出的数据搜索 while(edge != null){ int index = graph.vexnode[edge.index].data; //如果没有访问过 if(visited[index] == false){ visited[index] = true; result ++; //入栈 stack.push(index); } edge = edge.next; } } return result; } /* public static void print(MyGraph graph){ for(int i=0; i<graph.vexnum; i++){ System.out.println(i); Edge edge = graph.vexnode[i].firstedge; while(edge != null){ System.out.print(graph.vexnode[edge.index].data+1); edge = edge.next; } } } */ }
三、第三种做法:数组
可以直接用数组做出来:
1.建一个二维数组,如果认识则置为1,否则为0
2.首先将跟 1 一组的入栈
3.然后仿照深搜,计算得到结果。
package com.ct.graph; import java.util.Scanner; import java.util.Stack; /** * @author MoonMonster * @date 2015-10-16 下午03:52:27 */ public class Test { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int n, m; int T; T = sc.nextInt(); while(true){ if(T == 0){ break; } T --; n = sc.nextInt(); m = sc.nextInt(); System.out.println(count(n,m)); } } public static int count(int n, int m){ int result = 0; Stack<Integer> stack = new Stack<Integer>(); //因为是从1开始的,所以数组要为n+1 int[][] num = new int[n+1][n+1]; //判断该数是否已经加过 boolean visited[] = new boolean[n+1]; //初始化 for(int i=0; i<n+1; i++){ visited[i] = false; } //构建数组 for(int i=0; i<m; i++){ int a = sc.nextInt(); int b = sc.nextInt(); num[a][b] = 1; num[b][a] = 1; } //将跟'1'一组的数据压入栈 for(int i=0; i<n; i++){ if(num[1][i] != 0){ stack.push(i); } } while(!stack.empty()){ final int s = stack.pop(); //如果该数没被访问过 if(visited[s] == false){ result ++; visited[s] = true; //获得跟s一组的数 for(int i=0; i<n+1; i++){ //如果跟s一组且没有被访问 if(visited[i]==false && num[s][i]==1){ stack.push(i); } } } } return result - 1; } }
因为链接失效了,所以没法判断第二种和第三种做法的代码是否能得到正确结果(题目给出的测试数据通过了),但第一种肯定是通过了的。
深知自己能力之不足,所以若有谁偶然看到这篇博文,发现错误或有待提高之处,先谢谢各位的纠正,指出。
发表评论
-
jsp---隐式对象简单介绍
2016-03-02 12:25 3620什么是隐式对象? JSP的隐式对象是指在JSP页面系统中 ... -
工厂方法设计模式
2016-02-26 18:24 0一、什么是简单工厂 ... -
netty处理tcp粘包/拆包问题
2016-02-26 17:28 5221所谓的粘包/拆包,用一个例子来说明就是: 加入客户端向服 ... -
netty5服务端与客户端的构建
2016-02-25 19:55 3621简单的介绍一些服务端代码的编写顺序。 1.得到 Serv ... -
Java序列化的几种方式
2016-02-24 21:46 20731.自己定义方法 优点:不同预先设置缓存大小 缺点:不 ... -
Java --- 使用HttpURLConnection连接网络
2016-02-10 19:13 884package com.chalmers.httputils ... -
正则表达式---符号介绍及其简单使用方法
2016-02-07 13:13 710\\ 反斜杠 \t 间隔 ('\u0009') \n 换 ... -
正则表达式---符号介绍及其简单使用方法
2016-02-07 13:09 0\\ 反斜杠 \t 间隔 ('\u0009') \n 换 ... -
BMP24位格式图片读取
2016-01-13 18:01 825存在很大很大的问题, ... -
简单扫雷--完结
2015-12-27 21:50 848不再做了,最后一个版 ... -
简单扫雷--修改
2015-12-26 14:00 13跟上个版本相比较,改 ... -
简单扫雷
2015-12-25 00:50 14花了两个小时的时间,把扫雷的最基本的功能给实现了,虽然本 ... -
Socket_TCP 服务端编写
2015-12-17 22:26 797package com.ct.server; impo ... -
使用一个break跳出多重循环
2015-11-20 09:16 1710大家都知道,java中的bre ... -
Java框架集合--常见类的常用方法的常规使用
2015-10-26 00:16 2424Java框架集合--常见类的常用方法的常规使用 1.List ... -
Java框架集合--常见类的常用方法的常规使用
2015-10-26 00:14 01.List (1)ArrayList 与 Vector ... -
Java框架集合--常见类的常用方法的常规使用
2015-10-26 00:00 11.List (1)ArrayList 与 Vector ... -
Java框架集合--常见类的常用方法的常规使用
2015-10-25 23:48 01.List (1)ArrayList 与 Vector ... -
Java - - 数组实现栈基本功能
2015-10-24 23:52 1748package com.ct.stack; /** ... -
Java手写动态数组
2015-10-21 23:06 2295package com.ct.array; /** ...
相关推荐
毕业设计基于Python+PyQt5实现多智能体博弈AI五子棋游戏(包含人机博弈+深搜+α-β剪枝)源代码+文档说明,含有代码注释,新手也可看懂。毕业设计、期末大作业、课程设计、高分必看,下载下来,简单部署,就可以使用...
Python+PyQt5实现五子棋游戏(人机博弈+深搜+α-β剪枝) 该项目使用Pycharm 2021.2.3 + Python3.8编写 该五子棋游戏棋盘大小n = 15*15=255,假设搜索深度为d,使用深度优先搜索进行推演的时间复杂度为 $$ O(n^d)...
深度优先搜索(Deepth-First Search, DFS)则是一种图或树遍历的方法,常用于解决复杂结构的搜索问题,如迷宫求解、有向图的拓扑排序等。 结合标签“源码”和“工具”,我们可以推断这篇博客可能提供了解决POJ 1696...
深度搜索 回溯 int main { string s1 s2; while cin >> s1 >> s2 { count 0; cout << "[" << endl; if s1 length s2 length BackTrake s1 s2 ;... [更多]
对于没有父节点指针的普通二叉树,解决LCA的方法通常涉及到深度优先搜索(DFS)。我们可以从根节点开始,找到给定节点的路径,并存储在向量中。例如,假设我们有以下二叉树: ``` 10 / \ 6 14 / \ / \ 4 8 12 16 ...
<项目介绍> 五子棋是全国智力运动会竞技项目之一,是一种两人对弈的纯策略型棋类游戏。 五子棋的棋具与围棋通用,是一种传统的棋种,有两种玩法。 一种是双方分别使用黑白两色的棋子,下在棋盘直线与横线的交叉点...
在探讨“八数码 + 迭代深搜 +A*”这一主题时,我们触及的是算法设计与优化领域中一个非常具体且深入的概念。八数码问题(又称为8-puzzle),是一个经典的搜索问题,在一个3x3的棋盘上,有8个数字块和一个空格,目标...
标题中的“图的深搜+回溯练习题:POJ2197”是指一个编程题目,主要涉及图论中的深度优先搜索(DFS, Depth First Search)和回溯算法的应用。这个题目来源于在线编程竞赛平台POJ(Problem Online Judge),编号为2197...
标题中的“图的深搜+树状数组练习 POJ 3321(JAVA)”指的是一个编程题目,其中涉及到图的深度优先搜索(DFS, Depth First Search)算法和树状数组(也称为线段树,Segment Tree)的数据结构。这个题目来源于POJ...
前言 蚂蚁森林自动收集能量(上) 紧接上期,这期主要解释这个...如图所示 2.打开无障碍服务的代码 Settings.Secure.putString(getContentResolver(), Settings.Secure.ENABLED_ACCESSIBILITY_SERVICES, 包名/类名);
各种搜索算法,配合POJ上的题目,含标程,及各题解题思路。
用深搜(深度优先搜索-DFS)算法解数独。通过解数独这一实例,相信能让初学者更直观地理解深搜的功能和实现。
搜索算法是一种常用的解决问题的方法,当我们面临着无法通过建立数学模型解决的问题时,搜索算法能够帮助我们找到解决方案。搜索算法可以分为两大类:深搜和广搜。深搜是一种基于回溯思想的搜索算法,它从当前状态...
本话题将深入探讨一种利用深度优先搜索(Deepth First Search,简称DFS)解决图片填色问题的方法,特别是针对四色问题的应用。 四色问题,又称四色定理,是图论中的一个经典问题,它提出:任何平面图(无自相交边的...
在C++中,我们可以使用递归函数或者自定义栈来实现DFS,对于有向图和无向图,实现方法略有不同,但核心思想一致。 广度优先搜索(BFS)则是一种从起始节点开始,逐层探索所有相邻节点的算法。BFS使用队列数据结构,...
标题中的“上楼梯”是一个经典的计算机算法问题,通常在编程面试或算法竞赛中出现。它涉及到深度优先搜索...这些算法在实际的编程项目和面试中都十分常见,因此熟练掌握它们对于提升编程技能和解决问题能力至关重要。
### 第3章 深搜的剪枝技巧 #### 知识点概述 - **剪枝的基本概念**:剪枝是一种在搜索过程中优化算法的方法,主要用于减少搜索空间,提高算法效率。 - **剪枝的重要性**:对于信息学竞赛中常见的搜索类问题(如深搜...
### 第3章 深搜的剪枝技巧 #### 知识点概述 在计算机科学领域,特别是针对算法设计与优化方面,“深搜的剪枝技巧”是一个非常重要的概念。通常,深度优先搜索(DFS)作为一种基本的遍历或搜索算法,被广泛应用于多...
在IT领域,C语言是一种强大的、底层的编程语言,常用于...通过学习和理解这个项目,开发者不仅可以提升对C语言和数据结构的理解,还能掌握图形界面编程和算法可视化技能,这对于提升编程能力和解决问题的能力大有裨益。
【深搜相关题解】 深度优先搜索(Deep First Search, DFS)是一种用于遍历或搜索树或图的算法。在图或树结构中,DFS会尽可能深地探索节点的子树,直到达到叶子节点,然后回溯到最近的未访问节点,继续探索其他分支...