`
MoonMonster
  • 浏览: 36609 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

多种方法解决”图+深搜“编程题目

 
阅读更多
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给折腾出来了。

以下是代码:
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;
	}
}


因为链接失效了,所以没法判断第二种和第三种做法的代码是否能得到正确结果(题目给出的测试数据通过了),但第一种肯定是通过了的。



深知自己能力之不足,所以若有谁偶然看到这篇博文,发现错误或有待提高之处,先谢谢各位的纠正,指出。
  • 大小: 14.6 KB
1
2
分享到:
评论

相关推荐

    毕业设计基于Python+PyQt5实现多智能体博弈AI五子棋游戏(包含人机博弈+深搜+α-β剪枝)源代码+文档说明

    毕业设计基于Python+PyQt5实现多智能体博弈AI五子棋游戏(包含人机博弈+深搜+α-β剪枝)源代码+文档说明,含有代码注释,新手也可看懂。毕业设计、期末大作业、课程设计、高分必看,下载下来,简单部署,就可以使用...

    Python+PyQt5实现五子棋游戏(人机博弈+深搜+α-β剪枝)

    Python+PyQt5实现五子棋游戏(人机博弈+深搜+α-β剪枝) 该项目使用Pycharm 2021.2.3 + Python3.8编写 该五子棋游戏棋盘大小n = 15*15=255,假设搜索深度为d,使用深度优先搜索进行推演的时间复杂度为 $$ O(n^d)...

    极角排序:POJ 1696(叉积+深搜)

    深度优先搜索(Deepth-First Search, DFS)则是一种图或树遍历的方法,常用于解决复杂结构的搜索问题,如迷宫求解、有向图的拓扑排序等。 结合标签“源码”和“工具”,我们可以推断这篇博客可能提供了解决POJ 1696...

    ZOJ1004回溯+深搜

    深度搜索 回溯 int main { string s1 s2; while cin &gt;&gt; s1 &gt;&gt; s2 { count 0; cout &lt;&lt; &quot;[&quot; &lt;&lt; endl; if s1 length s2 length BackTrake s1 s2 ;... [更多]

    【POJ1330】最近公共祖先(LCA):并查集+深搜 - cxllyg的专栏 - 博客频道 - CSDN.NET1

    对于没有父节点指针的普通二叉树,解决LCA的方法通常涉及到深度优先搜索(DFS)。我们可以从根节点开始,找到给定节点的路径,并存储在向量中。例如,假设我们有以下二叉树: ``` 10 / \ 6 14 / \ / \ 4 8 12 16 ...

    毕业设计《基于Python+PyQt5实现多智能体博弈AI五子棋游戏(包含人机博弈+深搜+α-β剪枝)》+源代码+文档说明

    &lt;项目介绍&gt; 五子棋是全国智力运动会竞技项目之一,是一种两人对弈的纯策略型棋类游戏。 五子棋的棋具与围棋通用,是一种传统的棋种,有两种玩法。 一种是双方分别使用黑白两色的棋子,下在棋盘直线与横线的交叉点...

    八数码 + 迭代深搜 +A*

    在探讨“八数码 + 迭代深搜 +A*”这一主题时,我们触及的是算法设计与优化领域中一个非常具体且深入的概念。八数码问题(又称为8-puzzle),是一个经典的搜索问题,在一个3x3的棋盘上,有8个数字块和一个空格,目标...

    图的深搜+回溯练习题:POJ2197

    标题中的“图的深搜+回溯练习题:POJ2197”是指一个编程题目,主要涉及图论中的深度优先搜索(DFS, Depth First Search)和回溯算法的应用。这个题目来源于在线编程竞赛平台POJ(Problem Online Judge),编号为2197...

    图的深搜+树状数组练习 POJ 3321(JAVA)

    标题中的“图的深搜+树状数组练习 POJ 3321(JAVA)”指的是一个编程题目,其中涉及到图的深度优先搜索(DFS, Depth First Search)算法和树状数组(也称为线段树,Segment Tree)的数据结构。这个题目来源于POJ...

    安卓AccessibilityService实现蚂蚁森林自动收集能量 最新 多线程 + 手势 + 深搜webView(续)

    前言 蚂蚁森林自动收集能量(上) 紧接上期,这期主要解释这个...如图所示 2.打开无障碍服务的代码 Settings.Secure.putString(getContentResolver(), Settings.Secure.ENABLED_ACCESSIBILITY_SERVICES, 包名/类名);

    深搜+宽搜+剪枝 配合POJ题目

    各种搜索算法,配合POJ上的题目,含标程,及各题解题思路。

    深搜算法解数独

    用深搜(深度优先搜索-DFS)算法解数独。通过解数独这一实例,相信能让初学者更直观地理解深搜的功能和实现。

    搜索入门及深搜广搜演示

    搜索算法是一种常用的解决问题的方法,当我们面临着无法通过建立数学模型解决的问题时,搜索算法能够帮助我们找到解决方案。搜索算法可以分为两大类:深搜和广搜。深搜是一种基于回溯思想的搜索算法,它从当前状态...

    基于深搜的图片填色算法

    本话题将深入探讨一种利用深度优先搜索(Deepth First Search,简称DFS)解决图片填色问题的方法,特别是针对四色问题的应用。 四色问题,又称四色定理,是图论中的一个经典问题,它提出:任何平面图(无自相交边的...

    图的数据结构深搜/广搜

    在C++中,我们可以使用递归函数或者自定义栈来实现DFS,对于有向图和无向图,实现方法略有不同,但核心思想一致。 广度优先搜索(BFS)则是一种从起始节点开始,逐层探索所有相邻节点的算法。BFS使用队列数据结构,...

    上楼梯(深搜+回溯)JAVA解答

    标题中的“上楼梯”是一个经典的计算机算法问题,通常在编程面试或算法竞赛中出现。它涉及到深度优先搜索...这些算法在实际的编程项目和面试中都十分常见,因此熟练掌握它们对于提升编程技能和解决问题能力至关重要。

    第3章 深搜的剪枝技巧-2021.01.30.pdf

    ### 第3章 深搜的剪枝技巧 #### 知识点概述 - **剪枝的基本概念**:剪枝是一种在搜索过程中优化算法的方法,主要用于减少搜索空间,提高算法效率。 - **剪枝的重要性**:对于信息学竞赛中常见的搜索类问题(如深搜...

    第3章 深搜的剪枝技巧.pdf

    ### 第3章 深搜的剪枝技巧 #### 知识点概述 在计算机科学领域,特别是针对算法设计与优化方面,“深搜的剪枝技巧”是一个非常重要的概念。通常,深度优先搜索(DFS)作为一种基本的遍历或搜索算法,被广泛应用于多...

    c语言实现的,基于深搜和广搜,有界面显示

    在IT领域,C语言是一种强大的、底层的编程语言,常用于...通过学习和理解这个项目,开发者不仅可以提升对C语言和数据结构的理解,还能掌握图形界面编程和算法可视化技能,这对于提升编程能力和解决问题的能力大有裨益。

    深搜相关题解1

    【深搜相关题解】 深度优先搜索(Deep First Search, DFS)是一种用于遍历或搜索树或图的算法。在图或树结构中,DFS会尽可能深地探索节点的子树,直到达到叶子节点,然后回溯到最近的未访问节点,继续探索其他分支...

Global site tag (gtag.js) - Google Analytics