yxc大佬视频总结,链接如下. 视频中dfs与bfs报错原因其实相同两者算法都可以.
注释有点多,方便查看,大佬们不要介意啦...
dfs
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = N * 2; // 双向邻接表
int n; // 树的节点数量
int h[N], e[M], ne[M], idx; // 邻接表
// 邻接表插入 节点a -> b 的一条边
void add(int a, int b)
{
e[idx] = b; // 添加节点 b
ne[idx] = h[a]; // 此节点的 next 指针指向a
h[a] = idx++; // 邻接表 a 指向新建节点
}
// 深搜计数
int dfs(int u, int father)
{
int res = 1;
for(int i = h[u]; ~i; i = ne[i])
{
int son = e[i];
if(son != father) res += dfs(son, u);
}
return res;
}
int main()
{
cin >> n;
memset(h, -1, sizeof h);// 初始化邻接表, -1代表空指针
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; i = ne[i]) //遍历树根节点所有子节点 ~i 等价于 i!= 1
{
res = max(res, dfs(e[i], 1)); // 防止反向搜索父节点,将父节点传入
}
cout << res << endl;
return 0;
}
bfs
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = N * 2;
int n;
int h[N], e[M], ne[M], idx;
// bfs 队列 判重数组
int q[N];
bool st[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int bfs(int u)
{
int hh = 0, tt = 1; // 计数加1
q[0] = u;
st[u] = true;
while(hh <= tt)
{
int t = q[hh++]; // 每次取队列中一个元素 hh 加1,当 取的元素个数大于添加到队列的个数,循环结束
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if(!st[j])
{
q[++tt] = j;
st[j] = true;
}
}
}
return tt;
}
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;
st[1] = true;
for(int i = h[1]; ~i; i = ne[i])
{
res = max(res, bfs(e[i])); // 由于bfs中有判重数组,所以不需要传入父节点防止倒搜
}
cout << res << endl;
return 0;
}