【例77.1】模拟链表

解题思路

用head、to、next数组构成前向星，每条无向边添加两条有向记录，使用头插法。输出时从head沿next遍历，顺序为输入的逆序，与样例一致。

正确性说明

依照上述推导，逐步维护已处理部分的有效状态。每一步都完成当前项的贡献且不改变已确定的次序，结束时输出的状态恰好对应题目要求。

易错点

邻接表不能自行排序；无向边必须双向保存。

复杂度

时间O(n+m)，空间O(n+m)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> head(n + 1, -1), to(2 * m), next(2 * m), deg(n + 1);
    int idx = 0;
    auto edge = [&](int u, int v) {
        to[idx] = v;
        next[idx] = head[u];
        head[u] = idx++;
        deg[u]++;
    };
    while (m--) {
        int u, v;
        cin >> u >> v;
        edge(u, v);
        edge(v, u);
    }
    for (int u = 1; u <= n; u++) {
        cout << deg[u];
        for (int e = head[u]; e != -1; e = next[e])
            cout << " " << to[e];
        cout << "\n";
    }
    return 0;
}