3、DFS问题 & 树的重心

AcWing 846. 树的重心

树的数组单链表表示方法 dfs深搜

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.zhongxin();
    }

    int N = 200010;
    int M = 2 * N;
    int[] e = new int[N];
    int[] ne = new int[N];
    int[] h = new int[N];//head指针
    //e[h[a]]存储的是a的拉链头结点的结点值
    int idx = 1;

    void insert(int a, int b) {
        //将b点插到h[a]的后面
        //h[a]代表的是 a 这一点的head指针
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    HashMap<Integer, Integer> hashMap = new HashMap();

    int []sum=new int[N];
    TreeSet<Integer> treeSet=new TreeSet();
    int min=0;
    //start代表的是初始结点值
    void dfs(int start) {
        int head = h[start];
        hashMap.put(start, 1);
        sum[start]+=1;
        for (int i = head; i != -1; i = ne[i]) {
            if (!hashMap.containsKey(e[i])){
                dfs(e[i]);
                sum[start]+=sum[e[i]];
            }
        }
    }
    void dfs_max(int start) {
        hashMap.put(start, 1);
        int head = h[start];
        int max=0;
        for (int i = head; i != -1; i = ne[i]) {
            if (!hashMap.containsKey(e[i])){
                dfs_max(e[i]);
                if(!(sum[e[i]]>sum[start])){//证明不是父节点
                    if(sum[e[i]]>max){
                        max=sum[e[i]];
                    }
                }
            }
        }
        max=Math.max(max,sum[1]-sum[start]);
        treeSet.add(max);
    }

    void zhongxin() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Arrays.fill(h, -1);
        while (--n > 0) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            insert(a, b);
            insert(b, a);
        }

        dfs(1);
        hashMap.clear();
        dfs_max(1);
        System.out.println(treeSet.first());
    }
}

精简版，一次dfs

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.zhongxin();
    }

    int N = 200010;
    int[] e = new int[N];
    int[] ne = new int[N];
    int[] h = new int[N];//head指针
    //e[h[a]]存储的是a的拉链头结点的结点值
    int idx = 1;

    void insert(int a, int b) {
        //将b点插到h[a]的后面
        //h[a]代表的是 a 这一点的head指针
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    HashMap<Integer, Integer> hashMap = new HashMap();
    int[] sum = new int[N];
    int n = 0;
    TreeSet<Integer> treeSet = new TreeSet();

    //start代表的是初始结点值
    void dfs(int start) {
        hashMap.put(start, 1);
        sum[start] += 1;
        int max = 0;
        for (int i = h[start]; i != -1; i = ne[i]) {
            if (!hashMap.containsKey(e[i])) {
                dfs(e[i]);
                sum[start] += sum[e[i]];
                max = Math.max(sum[e[i]], max);

            }
        }
        max = Math.max(max, n - sum[start]);
        treeSet.add(max);
    }

    void zhongxin() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        Arrays.fill(h, -1);
        for (int i = 0; i < n-1; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            insert(a, b);
            insert(b, a);
        }
        dfs(1);
        System.out.println(treeSet.first());
    }
}