怀旧书本
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int M = 2 * N;
int n;
int head[N], Next[M], ver[M], tot;
bool vis[N];
int ans = INT_MAX;

void add(int a, int b) {
    ver[++tot] = b;
    Next[tot] = head[a];
    head[a] = tot;
}

int dfs(int u) {
    vis[u] = true;
    int sum = 1;
    int ca = 0;
    for (int i = head[u]; i != -1; i = Next[i]) {
        if (vis[ver[i]]) continue;
        int nsum = dfs(ver[i]);
        ca = max(ca, nsum);
        sum += nsum;
    }
    ca = max(ca, n - sum);
    ans = min(ca, ans);
    return sum;
}

int main() {
    memset(head, -1, sizeof head);
    cin >> n;
    for (int i = 0, a = 0, b = 0; i < n - 1; ++i) {
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    
    dfs(1);
    
    cout << ans << endl;
    
    return 0;
}
本文为原创文章,欢迎分享,勿全文转载,如果内容你实在喜欢,可以加入收藏夹,说不定哪天故事又继续更新了呢。
本文地址:https://qoogle.top/tree-dfs/
最后修改日期:2020年5月7日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。