图论之树的基础

树的定义

联通无环图，是个性质很好的数据结构

树的遍历

这里给出邻接表的写法，有其他写法待补充

#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 也就是父节点，防止搜回去
            if(to[i]!=pre) dfs(to[i], x);
    }
}
int main() {

    // n是点数，m是边数，实际上 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;
}

树的直径

定义

一棵树上最长的路径

这里给出代码，思路是从任意一个点出发，从他的所有子树找出一个最深的，和一个次深的，加一起即可。实际上下一种方法更优，小朋友们不要学我

#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;
}