树的重心.
感觉老师上课讲的还是有一点抽象,就换了一个思路
-
使用了一个
vector<int> ne[]
类型的数组,储存每一个节点的子节点. -
插入的时候将点插在对应的变长数组末尾,遍历的时候依次遍历对应的vector.
代码如下:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 100;
//ne用于储存所有的子节点
vector<int> ne[N];
//used数组储存该点是否被遍历过
bool used[N];
//sum是储存以对应节点为根的子树的节点数,包括节点本身
int sum[N];
//总节点数定义为全局变量,在计算ans进行比较时会用到.
int n;
//ans是重心最大连通块的最小值
int ans = N;
//由于是双向边,将两个点视为对方的子节点.
void ins(int a, int b)
{
ne[a].push_back(b);
ne[b].push_back(a);
}
void dfs(int u)
{
//先进行标记
used[u] = true;
//m是遍历到的点数最多的连通块的点数
int m = 0;
//sum[]先加上这个点本身.
sum[u] = 1;
//依次遍历每一个子节点.
for (int i = 0; i < ne[u].size(); i++)
{
int v = ne[u][i];
if (!used[v])
{
dfs(v);
//sum[u]加上刚刚遍历完的点下面所有点的数量
sum[u] += sum[v];
//比较出较大值
m = max(m, sum[v]);
}
}
//最终m和m父节点所在连通块点数进行比较.
m = max(m, n - sum[u]);
//ans得到最小值.
ans = min(m, ans);
}
int main()
{
ios::sync_with_stdio(0);
cin >> n;
for (int i = 0; i < n - 1; i++)
{
int a, b;
cin >> a >> b;
ins(a, b);
}
dfs(1);
cout << ans << endl;
return 0;
}