吝啬的国度--无向图，广度优先遍历，内存爆掉了

本文主要是介绍吝啬的国度--无向图，广度优先遍历，内存爆掉了，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

地址：http://acm.nyist.net/JudgeOnline/problem.php?pid=20

描述

在一个吝啬的国度里有N个城市，这N个城市间只有N-1条路把这个N个城市连接起来。现在，Tom在第S号城市，他有张该国地图，他想知道如果自己要去参观第T号城市，必须经过的前一个城市是几号城市（假设你不走重复的路）。

输入

第一行输入一个整数M表示测试数据共有M(1<=M<=5)组
每组测试数据的第一行输入一个正整数N(1<=N<=100000)和一个正整数S(1<=S<=100000)，N表示城市的总个数，S表示参观者所在城市的编号
随后的N-1行，每行有两个正整数a,b(1<=a,b<=N)，表示第a号城市和第b号城市之间有一条路连通。

输出

每组测试数据输N个正整数，其中，第i个数表示从S走到i号城市，必须要经过的上一个城市的编号。（其中i=S时，请输出-1）

样例输入

1
10 1
1 9
1 8
8 10
10 3
8 6
1 2
10 4
9 5
3 7

样例输出

-1 1 10 10 9 8 3 1 1 8

思路：不多说，~_~表示不知道题目说什么，不过当复习下知识点：向图，广度优先遍历吧。

附上自己的代码：居然超过了内存限制。。。苦逼~~~~,有时间再研究下，怎么优化

import java.util.ArrayList;
import java.util.Scanner;public class Main{public static void main(String[] args){Main main =new Main();main.solution();}public void solution(){Scanner cin=new Scanner(System.in);int n=cin.nextInt();while(n-->0){int allCity=cin.nextInt();int startCity=cin.nextInt();int [][] path=new int[allCity][allCity];for(int i=0;i<allCity-1;i++){	//是allCity-1条路，n座城市有n-1条路 --初始化数组，无向图int xi=cin.nextInt()-1;int xj=cin.nextInt()-1;path[xi][xj]=1;path[xj][xi]=1;}/*for(int[] a:path){for(int b:a)System.out.print(b);System.out.println();}*/ArrayList<Integer> queue=new ArrayList<Integer>();queue.add(startCity-1);while(queue.size()>0){	int tmp=queue.remove(0);for(int i=0;i<allCity;i++){	//进行广度优先遍历，由无向变成有向，即：将无根树变成有根树if(path[tmp][i]!=0){path[i][tmp]=0;queue.add(i);}}}for(int i=0;i<allCity;i++){		//寻找路径if(i==startCity-1)System.out.print("-1 ");else{for(int j=0;j<allCity;j++){if(path[j][i]!=0){System.out.print(j+1+" ");break;}}}}System.out.println();}}
}

最后附上java能ac的代码： http://blog.csdn.net/taotaotaotao910429/article/details/7850829 可以参考下。。不明白，模拟一遍就差不多了，感觉最直接的方法就是模拟一下，就知道整体式怎么一回事了

7.29号，今天对着能ac的代码又做了一遍，发现思路跟昨天是一样的，关键是怎么优化，将二维数组变为一维数组。用上强大的集合。。不过也是勉强的通过。

代码如下：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class result
{ArrayList<Integer>vector=new ArrayList<Integer>();
}
public class Main {static result results[];static int path[],start,citynumber;static boolean mark[];public static void bfs(){Queue<Integer>queue=new LinkedList<Integer>();queue.add(start);mark[start]=true;while(!queue.isEmpty()){int s=queue.remove();for(int i=0;i<results[s].vector.size();i++){if(!mark[results[s].vector.get(i)]){path[results[s].vector.get(i)]=s;mark[results[s].vector.get(i)]=true;queue.add(results[s].vector.get(i));}}}}public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int cases=scanner.nextInt();while(cases--!=0){citynumber=scanner.nextInt();start=scanner.nextInt();results=new result[citynumber+1];path=new int[citynumber+1];mark=new boolean[citynumber+1];Arrays.fill(path, -1);	//全部初始化为-1for(int i=0;i<=citynumber;i++){results[i]=new result();}for(int i=0;i<citynumber-1;i++){int x,y;x=scanner.nextInt();y=scanner.nextInt();results[x].vector.add(y);results[y].vector.add(x);}bfs();for(int i=1;i<=citynumber;i++){System.out.print(path[i]+" ");}}}
}

这篇关于吝啬的国度--无向图，广度优先遍历，内存爆掉了的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---