树的重心

05 Sep 2024 in Algorithm Pageviews

dfs

给定一颗树，树中包含 n 个节点(编号为 1 ~ n) 和 n - 1 条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义如下：重心是指树中的一个节点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式

第一行包含整数 n，表示树的节点数。

接下来 n - 1 行，每行包含两个整数 a 和 b 之间存在一条边。

输出格式

输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。

数据范围

1 <= n <= 10⁵

输入样例

9

1 2

1 7

1 4

2 8

2 5

4 3

3 9

4 6

输出样例

4

代码实现如下：

#include <bits/stdc++.h>

using namespace std;

int ans = INT_MAX;
constexpr int N = 100010;

class Solution {
public:
    Solution()
    {
        h.resize(N, -1);
        e.resize(2 * N, 0);
        nxt.resize(2 * N, 0);
        st.resize(N, false);
    }

    void add(int a, int b)
    {
		e[idx] = b;
        nxt[idx] = h[a];
        h[a] = idx++;
    }

    int dfs(int n, int u)
    {
        int res = 0;
        int sum = 1;
        st[u] = true;
        for (int i = h[u]; i != -1; i = nxt[i]) {
            int j = e[i];
            if (!st[j]) {
                int sum_ = dfs(n, j);
                res = max(res, sum_);
                sum += sum_;
            }
        }

        res = max(res, n - sum);
        ans = min(ans, res);
        return sum;
    }

private:
    vector<int> h;
    vector<int> e;
    vector<int> nxt;
    vector<bool> st;
    int idx = 0;
};

int main()
{
    int n = 0;
    cin >> n;
    Solution sol;
    for (int i = 0; i < n - 1; i++) {
        int a = 0;
        int b = 0;
        cin >> a >> b;
        sol.add(a, b);
        sol.add(b, a);
    }
    
    sol.dfs(n, 1);
    cout << ans;
    return 0;
}