算法

深度优先搜索常用模型

int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

思路

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1E5 + 10;
int head[N], value[N*2], nxt[N*2];
int n, idx;
void add(int a, int b){
    value[idx] = b;
    nxt[idx] = head[a];
    head[a] = idx ++ ;
}
void read(){
    memset(head, -1, sizeof head);
    scanf("%d", &n);
    int a, b;
    for(int i = 0; i < n - 1; i ++ ){
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
}
int ans = N;
bool st[N];
int dfs(int u){
    st[u] = true;
    int sum = 1;
    int res = 0;
    for(int i = head[u]; i != -1; i = nxt[i]){
        int p = value[i];
        if(st[p])   continue;
        int son = dfs(p);
        res = max(son, res);
        sum += son;
    }
    res = max(res, n - sum);
    ans = min(res, ans);
    return sum;
}
int main(){
    read();
    dfs(1);
    cout << ans << endl;
    return 0;
}