邻接表模板（算法竞赛进阶指南）

• 邻接表模板（算法竞赛进阶指南）
• 数组模拟邻接表
  • 书上的方法——边从 1 开始编号
  • y总的方法——边从 0 开始编号
• vector 代替邻接表保存有向图
• 例题
• 参考资料

数组模拟邻接表

这种方式在书上最常用。书上的方法和y总的方法有点小区别，但是用起来都是一样的，dfs 的时候记得选对起始点就好。

无向图和有向图区别就是，把一条边 (u, v, w) 看成 (u, v, w) 和 (v, u, w) 两条边调用 add 加入邻接表即可。

书上的方法——边从 1 开始编号

参考算法竞赛进阶指南第 63 页。

// head[x] = m 表示点 x 的邻接表的表头是编号为 m 的边
// ver[m] 表示编号为 m 的边的终点
// edge[m] 表示编号为 m 的边的权值
int head[N], ver[M], edge[M], Next[M], tot;

// 加入有向边 (x, y)，权值为 z
void add(int x, int y, int z) {
    // 真实数据
    ver[++tot] = y, edge[tot] = z;
    // 在表头 x 处插入
    Next[tot] = head[x], head[x] = tot;
}

// 访问从 x 出发的所有边
for (int i = head[x]; i; i = Next[i]) {
    int y = ver[i], z = edge[i];
    // 找到了一条有向边 (x, y)，权值为 z
}

注意到书上的边从 1 开始编号，所以不需要初始化 head 数组为 -1，用 0 表示终止节点。

y总的方法——边从 0 开始编号

这种方法和上面是等价的，但是要记得将 head 数组初始化为 -1。同时，在访问 x 出发的所有边的时候，终止条件不再是 i != 0，而是 i != -1，进一步 i != -1 可以简写为 ~i。

// 注意这里要初始化 head 为 -1
memset(head, 0xff, sizeof(head));

// 加入有向边 (x, y)，权值为 z
void add(int x, int y, int z) {
    // 真实数据
    ver[tot] = y, edge[tot] = z;
    // 在表头 x 处插入
    Next[tot] = head[x], head[x] = tot++;
}

// 访问从 x 出发的所有边，注意这里终止条件的不同
for (int i = head[x]; ~i; i = Next[i]) {
    int y = ver[i], z = edge[i];
    if (y != father) dfs(y, x, sum ^ z);
    // 找到了一条有向边 (x, y)，权值为 z
}

vector 代替邻接表保存有向图

书上第 458 页。

const int MAX_EDGES = 100010;
vector<int> ver[MAX_EDGES], edge[MAX_EDGES];

// 加入有向边 (x, y)，权值为 z
void add(int x, int y, int z) {
    ver[x].push_back(y);
    edge[x].push_back(z);
}

// 访问从 x 出发的所有边，注意这里终止条件的不同
for (int i = 0; i < ver[x].size(); i++) {
    int y = ver[x][i], z = edge[x][i];
    // 找到了一条有向边 (x, y)，权值为 z
}

例题

算法竞赛进阶指南打卡活动——144. 最长异或值路径

思路：

1. 先 DFS 求出根节点到每个点 x 的路径上所有边权的异或值 D(x)
2. 两个点 x 和 y 之间的所有边的边权异或值就是 D(x) xor D(y)，因为 x 到根和 y 到根这两条路径重叠的部分可以恰好抵消掉（a xor a = 0）。
3. 问题就变成了求从 D(1) 到 D(N) 选两个数，异或值最大，就是上一题最大异或对问题，用 Trie 求解即可。

代码 1：

#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 32 * N;

int n, u, v, w;
// 数组模拟邻接表常用形式
int head[N], ver[2 * N], edge[2 * N], Next[2 * N], tot;
int d[N];
int trie[M][2], p, q, tsize = 1;

// 加入有向边 (x, y)，权值为 z
void add(int x, int y, int z) {
    // 真实数据
    ver[++tot] = y, edge[tot] = z;
    // 在表头 x 处插入
    Next[tot] = head[x], head[x] = tot;
}
// father 防止回溯，sum 记下之前的异或总和
void dfs(int x, int father, int sum) {
    d[x] = sum;
    // 遍历 x 的所有边
    for (int i = head[x]; i; i = Next[i]) {
        int y = ver[i], z = edge[i];
        if (y != father) dfs(y, x, sum ^ z);
    }
}
// 查询某个数的和其最大异或对异或之后的值，并把这个值插入 Trie
int query(int a) {
    p = q = 1;
    int ans = 0;
    for (int i = 31; i >= 0; i--) {
        int j = a >> i & 1;
        if (trie[p][j] == 0) trie[p][j] = ++tsize;
        p = trie[p][j];
        // 寻找匹配，能够匹配一个不同的位的话
        if (trie[q][!j]) {
            ans |= 1 << i;
            q = trie[q][!j];
        } else {
            q = trie[q][j];
        }
    }
    return ans;
}
int main() {
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w), add(v, u, w);
    }
    dfs(1, -1, 0);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, query(d[i]));
    }
    cout << ans << endl;
    return 0;
}

代码 2：

#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 32 * N;

int n, u, v, w;
// 数组模拟邻接表常用形式
int head[N], ver[2 * N], edge[2 * N], Next[2 * N], tot;
int d[N];
int trie[M][2], p, q, tsize = 1;

// 加入有向边 (x, y)，权值为 z
void add(int x, int y, int z) {
    // 真实数据
    ver[tot] = y, edge[tot] = z;
    // 在表头 x 处插入
    Next[tot] = head[x], head[x] = tot++;
}
// father 防止回溯，sum 记下之前的异或总和
void dfs(int x, int father, int sum) {
    d[x] = sum;
    // 遍历 x 的所有边
    for (int i = head[x]; ~i; i = Next[i]) {
        int y = ver[i], z = edge[i];
        if (y != father) dfs(y, x, sum ^ z);
    }
}
// 查询某个数的和其最大异或对异或之后的值，并把这个值插入 Trie
int query(int a) {
    p = q = 1;
    int ans = 0;
    for (int i = 31; i >= 0; i--) {
        int j = a >> i & 1;
        if (trie[p][j] == 0) trie[p][j] = ++tsize;
        p = trie[p][j];
        // 寻找匹配，能够匹配一个不同的位的话
        if (trie[q][!j]) {
            ans |= 1 << i;
            q = trie[q][!j];
        } else {
            q = trie[q][j];
        }
    }
    return ans;
}
int main() {
    cin >> n;
    memset(head, 0xff, sizeof(head));
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w), add(v, u, w);
    }
    dfs(0, -1, 0);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, query(d[i]));
    }
    cout << ans << endl;
    return 0;
}

参考资料

1. yxc 常用代码模板3——搜索与图论
2. 算法竞赛进阶指南