题目描述
请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。
算法1
DFS
练习AC Saber时候的感受,记录一下,如下:
TLE,h[]忘记memset初始化
SE,遍历链表的时候,for循环 i = ne[i] 写成了i++
不出结果,忘记调用dfs(编程习惯后来经过调整,也是先把main函数的主要部分 输入输出都写出来,然后细扣自定义函数)
有一组大数据不过,ans开小了,开1e5是ok的,开0x3f3f3f3f是ok的,开0x3f是不行的
此题用到了最大值最小,先去max(res), 然后和ans比的时候用min
一道模板题,AC Saber里真正AC了可能会需要过4-5遍,耗时1-2小时
(一道题目,就要砸1-2小时,大神们真的是神,撵不上了…)
时间复杂度
$O(n^2)$
如果是n个点,n条边,树的DFS和BFS的时间复杂度都是O(n + m)
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;
int h[N], e[M], ne[M], idx;
bool st[N];
int n, ans = 0x3f3f3f3f;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dfs(int u)
{
st[u] = true;
int sum = 1, res = 0;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
int s = dfs(j);
res = max(res, s);
sum += s;
}
}
res = max(res, n - sum);
ans = min(res, ans);
return sum;
}
int main()
{
memset(h, -1, sizeof h);
cin >> n;
for (int i = 0; i < n - 1; i++)
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
dfs(1);
cout << ans << endl;
return 0;
}
复杂度是 O(n + m) 吧,每个点只会被遍历一次,每条边同理
是的,已修正
自我激励一下,next