跳转至

算法笔记

BISHI95 【模板】链式前向星

w3903771/algorithm

BISHI95　【模板】链式前向星¶

简单通过率 53.74%python3样例通过牛客 AC

牛客原题　源码

讲解章节：图的表示与遍历

一句话

无向图，按升序输出每个点的全部邻居。

解题思路¶

这题考什么¶

图的存储方式模板（见 90-图的表示与遍历）。 C++ 里链式前向星是「head[u] + nxt[] + to[] 三个数组模拟链表」，本质就是一个紧凑的邻接表，即 CSR（压缩稀疏行，用扁平数组连续存放所有邻居，再用一个偏移数组标出每个点的区间）。本题在存完之后还要求把每个点的邻居升序输出，所以存完还得排序。

Python 的实现选择（重点）¶

邻接表不要用 defaultdict(list)：1e5 个点时字典的哈希开销、以及 list 的按需扩容都会明显拖慢，而且顺序不确定；
这里直接开 adj = [[] for _ in range(n+1)] 的定长 list of list，下标即点号，append 是 O(1) 均摊；（也可以照搬链式前向星的三数组写法，但在 Python 里遍历链表指针反而比遍历 list 慢，list of list 才是等价且更快的实现。）
每个点的邻居单独 sort，总代价 Σ deg(u) log deg(u) <= O(m log m)。

数据规模与复杂度¶

n, m <= 1e5 -> 无向边共 2e5 个方向。建表 O(n + m)，排序 O(m log m)，输出 O(n + m)。

Python 的坑¶

输出有 n 行、总计 2e5 个数字，必须先拼成一个大字符串再一次 write；逐行 print 在 1e5 行时会明显变慢；
孤立点要输出 "None"（首字母大写），别输出空行；
题面没有说「不存在重边 / 自环」。链式前向星的本义是如实存下每条边，所以这里不做去重：给了两条 1-2 就输出两个 2；若出现自环 a==b，按无向图的存法会在 a 的邻居里出现两次 a—— 这与「照抄边表」的模板语义一致。

参考实现¶

solutions/BISHI95.py
import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    adj = [[] for _ in range(n + 1)]     # 定长 list of list，不用 defaultdict

    # ---- 读边：无向图，两个方向都要挂上 ----
    p = 2
    for _ in range(m):
        a = int(data[p]); b = int(data[p + 1]); p += 2
        adj[a].append(b)
        adj[b].append(a)

    # ---- 按点号从小到大逐行输出邻居 ----
    out = []
    for u in range(1, n + 1):
        e = adj[u]
        if e:
            e.sort()                     # 题目要求升序；单点排序代价 deg log deg
            out.append(" ".join(map(str, e)))
        else:
            out.append("None")           # 孤立点，注意首字母大写
    sys.stdout.write("\n".join(out) + "\n")


main()