首页 > 代码库 > NYOJ题目20吝啬的国度
NYOJ题目20吝啬的国度
-----------------------------------------
n-1条边的无向连通图是一棵树,又因为树上两点之间的路径是唯一的,所以解是唯一的。(注意并不一定是二叉树,所以最好采用存储图的方式存储数,我使用的是邻接表)
这个时候只需要考虑如何求解两点间的路径呢?遍历就可以了。
但是应该如何遍历呢?比较容易想到的办法是分别从每个点计算到S点的路径,既然它们的终点相同,那为什么不逆向一下干脆从S点向这些点出发呢?
所以现在问题就转化为了从S点出发遍历树,OK,这个问题就比较简单了,只需要在即将到达目的地之前记录一下就可以了。
对了,还需要注意一下的是猜测南阳OJ的JDK编译级别应该是<1.6的,因为使用new ArrayList<>()新特性的时候报语法错误了,不加即可,反正也会被擦除的。
AC代码:
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int times=sc.nextInt(); while(times-->0){ int n=sc.nextInt(); int s=sc.nextInt()-1; tree=new ArrayList[n]; for(int i=0;i<tree.length;i++) tree[i]=new ArrayList(); visited=new boolean[n]; must=new int[n]; for(int i=1;i<n;i++){ int v=sc.nextInt()-1; int u=sc.nextInt()-1; tree[v].add(u); tree[u].add(v); } must[s]=-1; dfs(s); for(int i=0;i<must.length;i++){ System.out.print(must[i]+" "); } System.out.println(); } } private static List<Integer> tree[]; private static boolean visited[]; private static int must[]; public static void dfs(int i){ visited[i]=true; for(Integer next:tree[i]){ if(visited[next]) continue; must[next]=i+1; dfs(next); } } }
题目来源: http://acm.nyist.net/JudgeOnline/problem.php?pid=20
NYOJ题目20吝啬的国度
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。