樹的定義

聯(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;
}