樹的定義
聯(lián)通無環(huán)圖，是個性質(zhì)很好的數(shù)據(jù)結(jié)構(gòu)
樹的遍歷
這里給出鄰接表的寫法撼班，有其他寫法待補(bǔ)充
#include <iostream>
using namespace std;
const int MAXN = 1000;
namespace tree {
int next[MAXN<<1], to[MAXN<<1], head[MAXN<<1], ce;
void add(int x, int y) {
to[++ce] = y; next[ce] = head[x]; head[x] = ce;
to[++ce] = x; next[ce] = head[y]; head[y] = ce;
}
void dfs(int x, int pre) {
for(int i=head[x]; i; i=next[i])
// 判斷下 pre 也就是父節(jié)點(diǎn)灵汪，防止搜回去
if(to[i]!=pre) dfs(to[i], x);
}
}
int main() {
// n是點(diǎn)數(shù)，m是邊數(shù)怒允，實(shí)際上 m=n-1 可以不作輸入
int n, m;
cin >> n >> m;
// 加邊
for(int i=1; i<=m; i++) {
int u, v; cin >> u >> v;
tree::add(u, v);
}
// 深搜出奇跡
tree::dfs(1, 0);
return 0;
}
樹的直徑
定義
一棵樹上最長的路徑
這里給出代碼埂软，思路是從任意一個點(diǎn)出發(fā)，從他的所有子樹找出一個最深的纫事，和一個次深的勘畔，加一起即可。實(shí)際上下一種方法更優(yōu)丽惶，小朋友們不要學(xué)我
#include <iostream>
using namespace std;
const int MAXN = 1000;
namespace tree {
int next[MAXN<<1], to[MAXN<<1], head[MAXN<<1], ce;
int h, h1, h2;
void add(int x, int y) {
to[++ce] = y; next[ce] = head[x]; head[x] = ce;
to[++ce] = x; next[ce] = head[y]; head[y] = ce;
}
void dfs(int x, int pre, int deep) {
h = max(h, deep);
for(int i=head[x]; i; i=next[i])
if(to[i]!=pre) dfs(to[i], x, deep + 1);
}
int getH(int x) {
for(int i=head[x]; i; i=next[i]) {
dfs(to[i], x, 1);
if(h > h1) h1 = h;
else if(h > h2) h2 = h;
h = 0;
}
int t = h1 + h2;
h1 = h2 = 0;
return t;
}
}
int main() {
int n, m;
cin >> n >> m;
for(int i=1; i<=m; i++) {
int u, v; cin >> u >> v;
tree::add(u, v);
}
int ans = 0;
for(int i=1; i<=n; i++)
ans = max(ans , tree::getH(i));
cout << ans << endl;
return 0;
}
