题解 | #【模板】链式前向星#

题目链接

【模板】链式前向星

题目描述

给定一个无向图，包含 $n$ 个点、 $m$ 条边（点编号 $1\sim n$ ）。接下来给出 $m$ 对 $u,v$ 表示无向边。请输出每个点直接相连的点编号（邻接点），并按升序输出；若某点无邻接点，输出 None。

输入：

第一行两个正整数 $n$ 、 $m$
接下来 $m$ 行，每行两个整数 $u$ 、 $v$ 表示一条无向边

输出：

输出 $n$ 行。第 $i$ 行为与点 $i$ 相邻的所有点的升序序列，空格分隔；若无相邻点输出 None

解题思路

使用链式前向星（压缩邻接表）存图：对每条无向边 $(u,v)$ 分别向 $u$ 、 $v$ 的表头插入一条单向边。
为保证升序输出，对每个点 $i$ ，遍历其前向星链表收集邻居到临时数组，排序后输出。
总复杂度：收集合计 $\mathcal{O}(m)$ ，排序总代价为按各点度数求和的 $\sum \deg(i)\log\deg(i) \le \mathcal{O}(m\log m)$ 。

代码

c++
java
python

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> head(n + 1, -1), to, nxt;
    to.reserve(2LL * m + 5);
    nxt.reserve(2LL * m + 5);
    int idx = 0;
    auto add_edge = [&](int u, int v) {
        to.push_back(v);
        nxt.push_back(head[u]);
        head[u] = idx++;
    };
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }
    vector<int> buf;
    for (int u = 1; u <= n; ++u) {
        buf.clear();
        for (int e = head[u]; e != -1; e = nxt[e]) buf.push_back(to[e]);
        if (buf.empty()) {
            cout << "None" << "\n";
        } else {
            sort(buf.begin(), buf.end());
            for (int i = 0; i < (int)buf.size(); ++i) {
                if (i) cout << ' ';
                cout << buf[i];
            }
            cout << "\n";
        }
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        List<Integer>[] g = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) g[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            g[u].add(v);
            g[v].add(u);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if (g[i].isEmpty()) {
                sb.append("None").append('\n');
            } else {
                Collections.sort(g[i]);
                for (int k = 0; k < g[i].size(); k++) {
                    if (k > 0) sb.append(' ');
                    sb.append(g[i].get(k));
                }
                sb.append('\n');
            }
        }
        System.out.print(sb.toString());
    }
}

n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)
for i in range(1, n + 1):
    if not g[i]:
        print('None')
    else:
        g[i].sort()
        print(' '.join(map(str, g[i])))

算法及复杂度

算法：链式前向星建图，按点收集邻接点并排序
时间复杂度： $\mathcal{O}(m \cdot \log m)$ （总排序开销上界），建图与遍历为 $\mathcal{O}(n + m)$
空间复杂度： $\mathcal{O}(n + m)$