搜索与图论第三期树与图的深度优先遍历-Toy模板网

这篇具有很好参考价值的文章主要介绍了搜索与图论第三期树与图的深度优先遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

该部分内容实际上是DFS的一个扩展，只要是会了DFS之后，这部分其实也差不多，直接上例题啦就。

1.例题：

文章来源地址https://www.toymoban.com/news/detail-801499.html

2.AC代码：

#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;//根链表定义变量一样,h[N]是head,有n个链表
bool st[N];
int ans = N;//全局答案

//链表插入操作
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;
	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i];
		if (!st[j]) {//如果还没有被搜过
			int s = dfs(j);//s表示当前这个子树的大小
			res = max(res, s);//子树中最大的
			sum += s;//以这个儿子为根节点的子树是以u为根节点的一部分
		}
	}
	res = max(res, n - sum);//以u为根节点的子树和剩余的连通块取最大值,
	//res存的就是把u删掉之后,各个连通块中点数的最大值
	ans = min(ans, res);//就是求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);
	cout << ans << endl;
	return 0;
}