树与图的深度优先遍历

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = N * 2;//因为需要建立两份边，所以 M = 2 * N;
int n;
int h[N], e[M], ne[M], idx;
int ans = N;
bool st[N];
//添加边的模板，要求熟练的默写，这部分的解释在 链表 专题中
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
//返回以u为根的子树中节点的个数，包括u节点
int dfs(int u)
{
    st[u] = true;
    int size = 0, sum = 0;//size存储的是以u为根的数的一个子儿子的节点数的最大值
    //sun存储以u为根的树的节点数, 包括u
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (st[j]) continue;
        int s = dfs(j);    //s存储的就是以 j 为根的子树的节点数，包括 j
        size = max(size, s);  //每次找出最大的子图的节点数
        sum += s;  //以j为根的树的节点数
    }
    size = max(size, n - sum - 1); //求 dfs 遍历的所有子树中最大的节点数的个数和 dfs 未遍历的那棵树的节点数的最大值
    ans = min(ans, size);
    return sum + 1;   //这里返回的个数加上根节点
}
int main()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a); //处理无向图的添边方式
    }
    dfs(1); //可以选择任意一个点开始进行 dfs，又u <= n，且 n 的最小值为1，所以只能从 1 开始
      //当然本题数据是从 5 开始的，所以对于本题写 dfs (1 ~ 5)均可AC
    printf("%d\n", ans);
    return 0;
}