noj 吝啬的国度

本文主要是介绍noj 吝啬的国度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

建立一个双向的图，从出发点遍历一遍用数组存储上一个顶点即可。

import java.util.*;
public class Main 
{
static List<Integer> list;
static Map<Integer,List<Integer>> map;
static void store(int a,int b)
{
list=map.get(a);
if(list==null) list=new ArrayList<Integer>();
list.add(b);
map.put(a, list);
}
static void before(int n,int s,Map<Integer,List<Integer>> map)
{
int pre[]=new int[n+1];
boolean vis[]=new boolean[n+1];
int key=s;
vis[key]=true;
List<Integer> list=map.get(s);
for(int k=0;k<list.size();k++) pre[list.get(k)]=key;
Queue<List<Integer>> q=new LinkedList<List<Integer>>();
q.offer(list);
while(!q.isEmpty())
{
List<Integer> lis=q.poll();
for(int i=0;i<lis.size();i++)
{
key=lis.get(i);
if(!vis[key])
{
vis[key]=true;
List<Integer> value=map.get(key);
q.offer(value);
for(int k=0;k<value.size();k++) 
{
int t=value.get(k);
if(!vis[t])pre[t]=key;
}
}			
}
}	
pre[s]=-1;
for(int i=1;i<n;i++) System.out.print(pre[i]+" ");
System.out.println(pre[n]);
}
public static void main(String[] args)
{
Scanner cin=new Scanner(System.in);
int m=cin.nextInt();
while(m--!=0)
{
map=new HashMap<Integer,List<Integer>>();
int n=cin.nextInt();
int s=cin.nextInt();
for(int i=1;i<n;i++)
{
int a=cin.nextInt();
int b=cin.nextInt();
store(a,b);
store(b,a);
}
before(n,s,map);		
}
}
}

这篇关于noj 吝啬的国度的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---