前言
該部分內(nèi)容實際上是DFS的一個擴展，只要是會了DFS之后，這部分其實也差不多，直接上例題啦就。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
1.例題：
文章來源地址http://www.zghlxwxcb.cn/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為根的子樹中點的數(shù)量
int dfs(int u) {
st[u] = true;//標(biāo)記一下,已經(jīng)被搜過了
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表示當(dāng)前這個子樹的大小
res = max(res, s);//子樹中最大的
sum += s;//以這個兒子為根節(jié)點的子樹是以u為根節(jié)點的一部分
}
}
res = max(res, n - sum);//以u為根節(jié)點的子樹和剩余的連通塊取最大值,
//res存的就是把u刪掉之后,各個連通塊中點數(shù)的最大值
ans = min(ans, res);//就是求res中的最小值,也就是數(shù)的重心
return sum;
}
int main() {
cin >> n;
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i++) {//構(gòu)圖
int a, b;
cin >> a >> b;
add(a, b), add(b, a);//無向邊
}
dfs(1);
cout << ans << endl;
return 0;
}總結(jié)
這部分較為簡單感謝大家的觀看，謝謝大家?。。?/h3>
文章來源：http://www.zghlxwxcb.cn/news/detail-801499.html
到了這里，關(guān)于搜索與圖論第三期 樹與圖的深度優(yōu)先遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
