题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

Java代码 简单易懂

import java.io.*;
import java.util.*;
import java.math.*;
    /*树是一种特殊的图
        无环连通图           
        图分为两种  有向图和无向图
            有向图的边是有方向的  a→b
            无向图的边是没方向的  a-b a可以走到b  b可以走到a                                      
        */ 
    public class Main {
    public static int N = 100010;//数据范围
    public static int ans = N;//全局答案 最小的最大值
    public static int M = N*2;//以有向图的格式存储无向图，所以每个节点至多对应2n-2条边
    public static int n,idx;//题目所给的输入，n个节点 //单链表指针
    public static int [] h = new int [N];//邻接表存储树，有n个节点，所以需要n个队列头节点
    public static int [] e = new int [M];//存储元素
    public static int [] ne = new int [M];//存储列表的next值
    public static boolean [] st = new boolean [N]; //存储已经遍历的点

public static void main(String[] args)throws IOException{
    BufferedReader re = new BufferedReader(new InputStreamReader(System.in));   

     n = Integer.parseInt(re.readLine());
    //初始化链表         
    Arrays.fill(h,-1);

    //构造树
    for(int i = 0;i<n-1;i++) {      
    String str [] = re.readLine().split(" ");
    int a,b;
    a = Integer.parseInt(str[0]);
    b = Integer.parseInt(str[1]);       

        add(a,b);
        add(b,a);
    }   
    dfs(1);
    System.out.println(ans);
}

//添加一条边
public static void add(int a, int b) {
    e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}


//返回以u为根的子树中节点的个数，包括u节点
public static int dfs(int u) {
//存储 删掉某个节点之后，最大的连通子图节点数
    int res = 0;
  st[u] = true; //标记访问过u节点
    int sum = 1; //存储 以u为根的树 的节点数, 包括u，如图中的4号节点

  //访问u的每个子节点
  for (int i = h[u]; i != -1; i = ne[i]) {
      int j = e[i];
      //因为每个节点的编号都是不一样的，所以 用编号为下标 来标记是否被访问过
      if (!st[j]) {
          int s = dfs(j);  // u节点的单棵子树节点数 如图中的size值
          res = Math.max(res, s); // 记录最大联通子图的节点数
          sum += s; //以j为根的树 的节点数
      }
  }
 // System.out.print("sum" + sum); System.out.print("ans" + ans); System.out.print("res" + res);  System.out.println("n-sum" + (n-sum)); 
  res = Math.max(res, n - sum); 
  ans = Math.min(res, ans); 
  return sum;
    }
}

```