这道题可以枚举每一个点 先统计他的每一个子节点的节点数 找到节点数最大的子节点 同时把所有子节点的数量加起来 记作x。 这个时候判断一下这一个点是不是root 如果不是root 就用n - x - 1(n是总节点数, 1 是枚举到的这个节点本身) 再和刚刚节点数最大的子节点取max
如此循环,取最小的最大值。 DFS或者BFS皆可。
还有在输入的时候统计每一个节点是否有parent 所以可以通过这个判断 如果一个输入a b但是b已经有parent了,那这个时候实际上应该储存为b -> a 反之则为 a -> b。这样能确保存储的是一颗树的结构 所以不管是bfs还是dfs都不需要打标记st了。
代码:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 100010;
struct Node {
int parent = -1;
vector<int> childnodes;
}tree[N];
void addChild(int p, int c) {
tree[p].childnodes.push_back(c);
tree[c].parent = p;
}
int bfs(int x) {
queue<int> q;
q.push(x);
int cnt = 0;
while(q.size()) {
int h = q.front();
cnt++;
q.pop();
for(auto j : tree[h].childnodes)
q.push(j);
}
return cnt;
}
int dfs(int x) {
if(tree[x].childnodes.size() == 0)
return 1;
int cnt = 1;
for(auto i : tree[x].childnodes)
cnt += dfs(i);
return cnt;
}
int main() {
int n;
cin >> n;
for(int i = 0;i < n-1;i ++) {
int p, c;
cin >> p >> c;
if(tree[c].parent != -1) addChild(c, p);
else addChild(p, c);
}
int res = 100010;
for(int i = 1;i <= n;i ++) {
int t = 0, cnt = 0;
for(auto j : tree[i].childnodes) {
int x = dfs(j); // both dfs and bfs works
t = max(t, x);
cnt += x;
}
if(tree[i].parent != -1)
t = max(n - cnt - 1, t);
res = min(t, res);
}
cout << res;
return 0;
}