AcWing 681. 疏散人群
原题链接
简单
作者:
跟着灿哥学切菜
,
2021-02-07 00:45:01
,
所有人可见
,
阅读 441
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = N * 2;
int n;
int h[N], e[M], ne[M], idx;
int q[N];
bool st[N];
//此时使用数组来模拟邻接表的存储方式
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
//使用dfs()的方式来进行遍历
int dfs(int u, int father) {
//首先当前u这个节点的个数已经有了1个
int res = 1;
//遍历u的所有的出边
for (int i = h[u]; i != -1; i = ne[i]) {
//取出当前节点的儿子节点
int son = e[i];
//如果此时的儿子不是父节点, 此时从这个节点继续继续进行深搜
//此时dfs()函数返回的是以u为根节点的子树中的节点的个数
if (son != father) res += dfs(son, u);
}
return res;
}
//使用bfs()的方式来遍历
int bfs(int u) {
int hh = 0, tt = 0;
//首先将u加到队列中
q[0] = u;
//将这个节点标记为已读
st[u] = true;
//当队列不为空的时候
while (hh <= tt) {
int t = q[hh ++];
for (int i = h[t]; i != -1; i = ne[i]) {
int son = e[i];
//如果此时没有被搜索过, 此时将这个节点加入到队列当中
if (!st[son]) {
q[++ tt] = son;
st[son] = true;
}
}
}
//最后将尾巴加上1, 表示的是队列中的节点的个数
return tt + 1;
}
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);
}
//计算根节点的每一个子树中的节点的最大值
int res = 0;
//遍历根节点
for (int i = h[1]; i != -1; i = ne[i]) {
//此时因为是无向图, 所以此时需要将father传入, 保证不会回过头来进行重复扫描
//每一次判断下一个节点是否是当前节点的父节点, 如果是, 则不进行搜索
res = max(res, dfs(e[i], 1));
}
cout << res << endl;
return 0;
}