java实现stl建树的方法,就是类似于c++那样,创建一个list数组,将元素压入到指定的list[x]中
在dfs函数中可以进行调用,实现遍历这个树
list数组建树:
- import java.util.*;
- public class Main{
- static List[] list=new ArrayList[100005];
- public static void main(String[] args) {
- Scanner cin=new Scanner(System.in);
- int n=cin.nextInt();
- for(int i=0;i<=n;i++) list[i]=new ArrayList();
- for(int i=1;i<n;i++){
- int x=cin.nextInt();
- int y=cin.nextInt();
- list[x].add(y);list[y].add(x); //两边压入
- }
- dfs(1,0);
- }
- static void dfs(int d,int pre){ //d是顶点,pre是父点
- System.out.println(d);
- int l=list[d].size();
- for(int i=0;i<l;i++){
- int son=(int)list[d].get(i);
- if(son!=pre){ //不为父点则进入
- dfs(son,d);
- }
- }
- }
- }
- /*
- 4
- 1 2
- 2 3
- 2 4
- */
同c++,二维list并不能很好实现树的建立,需要提前压入多个list后才可。
但是java的二维list可能真不行,因为非数组形式的二维list无法继续压入
即数组形式可实现:list[x].add(10)
二维形式要这样:list.get(x).add(10)
可以看到get函数返回的不是可改的对象,是一个仅可读的对象,没有listx]的指针不能进行压入。
java建树的方法还有map建树:
主要就是类似于c++的map<int,vector<int>> mp;去映射一个序列,没有上面好用仅做了解即可
- map = new HashMap<>();
- for(int i = 1; i <= N; i++) map.put(i, new ArrayList<>()); //指定下标压入一个序列
- import java.util.*;
-
- //某树形DP题代码
-
- public class Main{
- static int[] h;
- static Map<Integer, List<Integer>> map;
- static int[][] f;
- public static void main(String[] args){
- Scanner sc = new Scanner(System.in);
- int N = sc.nextInt();
- h = new int[N + 1];
- map = new HashMap<>();
- int root = (N + 1) * N / 2;
- for(int i = 1; i <= N; i++) map.put(i, new ArrayList<>());
- for(int i = 1; i <= N; i++) h[i] = sc.nextInt();
- for(int i = 1; i <= N - 1; i++){
- int l = sc.nextInt(), k = sc.nextInt();
- root -= l;
- map.get(k).add(l);
- }
- f = new int[N + 1][2];
- dfs(root);
- System.out.println(Math.max(f[root][0], f[root][1]));
- }
- static void dfs(int x){
- f[x][1] = h[x];
- for(int son: map.get(x)){
- dfs(son);
- f[x][0] += Math.max(f[son][0], f[son][1]);
- f[x][1] += f[son][0];
- }
- }
- }