时间复杂度
O(n+m)
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = N * 2;
int n;
int h[N], e[M], ne[M], idx;
bool st[N];
int ans = N;//ans存的就是最小的最大值,也就是答案~
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
//返回以u为根节点的自述中点的数量。
int dfs(int u){
st[u] = true;//标记当前这个点已经被搜过了。
int sum = 1, res = 0;
//sum记录当前子树的大小,res村的是把这个点删除之后所有的连通块中点数最大的那个连通块中的点数。
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];//j存的是当前链表里面的结点它对应的图里面的结点的编号是多少。
if(!st[j]){
int s = dfs(j);//用s表示当前子树的大小
res = max(res, s);//max算的是这个被删除的结点下面几个连通块所包含的点数的较大值。
sum += s;
}
}
res = max (res, n - sum);//这一步的n - num的含义是上面第三个连通块所包含的点数。
ans = min(ans, res);
return sum;
}
int main()
{
cin >> n;
memset(h, -1, sizeof h);
for(int i = 0; i < n - 1; i ++){
int a, b;
cin >>a >> b;
add(a, b), add(b, a);//因为是无向边,所以要加入两条边
}
dfs(1);//从编号为1的点开始搜
cout << ans << endl;
return 0;
}
//思路:对于每一个点,把这个点删除之后,统计剩余的每个联通块所包含的点数,把那个包含最多点数的连通块的点数给记录下来(尚且叫做*),之后把*进行一个二次比较,把最小的那个*拿出来作为答案输出就可以了
//这只是听严总题目讲解视频的笔记,还不懂呢(龇个大牙~2024.4.21)