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

题目链接

题目描述

给定一个包含 $N$ 个点、 $M$ 条边的无向图。点的编号从 1 到 $N$ 。你需要对于每个点，升序输出其所有直接相连的点的编号。如果一个点没有任何邻居，则输出 "None"。

解题思路

本题的本质是图的存储与遍历。我们需要一种数据结构来表示图，然后遍历这个结构来找到每个点的所有邻居。

在 C++ 中，最直接的方法是使用 std::vector<std::vector<int>> adj，其中 adj[i] 存储了节点 $i$ 的所有邻居。然而，在传统的算法竞赛中，链式前向星是一种更常用、空间效率更高、且在某些情况下遍历速度更快的静态图存储方法。

链式前向星详解

链式前向星通过数组模拟了邻接表的“拉链”结构，它主要由三部分构成：

head 数组: head[u] 存储以节点 $u$ 为起点的第一条边在 edge 数组中的索引。可以理解为每个邻接链表的“头指针”。初始时，所有 head 元素都应设为一个特殊值（如 -1），表示该点还没有出边。
edge 结构体数组: edge[i] 存储了图中的第 $i$ 条边。每条边包含两个核心信息：
- to: 这条边的终点。
- next: 与这条边起点相同的下一条边在 edge 数组中的索引。这相当于链表的 next 指针，将从同一个点出发的所有边串联起来。
idx 计数器: 一个整数，用于记录当前已经添加了多少条边，并作为新边在 edge 数组中的索引。

工作流程

添加边 (u, v):
1. 新边 edge[idx] 的终点 to 设置为 $v$ 。
2. 将新边的 next 指针指向旧的链表头：edge[idx].next = head[u]。
3. 更新链表头，使其指向新的边：head[u] = idx。
4. idx 自增。这个过程被称为“头插法”，新来的边总是在链表的最前面。对于无向图，需要添加两次边：(u, v) 和 (v, u)。
遍历节点 u 的所有邻居:
1. 从链表头开始：i = head[u]。
2. 只要 i 不是 -1，就不断地访问 edge[i]。
3. 邻居节点就是 edge[i].to。
4. 然后通过 next 指针移动到下一条边：i = edge[i].next。

本题解法

读入 $N$ 和 $M$ ，根据数据范围（ $10^5$ ）初始化链式前向星所需的数组。
循环 $M$ 次，每次读入一条边 $(u, v)$ ，并调用 add 函数两次，分别添加 u 到 v 和 v 到 u 的有向边，以此来表示无向边。
从 $i=1$ 到 $N$ 循环，对于每个节点 $i$ ： a. 创建一个临时列表（如 std::vector）来存储其所有邻居。 b. 使用链式前向星的遍历方法，将所有邻居 edge[j].to 存入临时列表。 c. 对临时列表进行排序。 d. 检查列表是否为空。如果为空，输出 "None"；否则，按格式输出列表中的所有邻居。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100005, M = 200005; // M条无向边 -> 2*M条有向边

struct Edge {
    int to, next;
} edges[M];

int head[N], idx;

void add(int u, int v) {
    edges[idx].to = v;
    edges[idx].next = head[u];
    head[u] = idx++;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    memset(head, -1, sizeof(head));
    idx = 0;

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }

    for (int i = 1; i <= n; ++i) {
        vector<int> neighbors;
        for (int j = head[i]; j != -1; j = edges[j].next) {
            neighbors.push_back(edges[j].to);
        }
        sort(neighbors.begin(), neighbors.end());

        if (neighbors.empty()) {
            cout << "None\n";
        } else {
            for (int k = 0; k < neighbors.size(); ++k) {
                cout << neighbors[k] << (k == neighbors.size() - 1 ? "" : " ");
            }
            cout << "\n";
        }
    }

    return 0;
}

import java.util.*;

public class Main {
    static final int N = 100005, M = 200005;
    static int[] head = new int[N];
    static int[] to = new int[M];
    static int[] next = new int[M];
    static int idx;

    public static void add(int u, int v) {
        to[idx] = v;
        next[idx] = head[u];
        head[u] = idx++;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        Arrays.fill(head, -1);
        idx = 0;

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            add(u, v);
            add(v, u);
        }

        for (int i = 1; i <= n; i++) {
            List<Integer> neighbors = new ArrayList<>();
            for (int j = head[i]; j != -1; j = next[j]) {
                neighbors.add(to[j]);
            }
            Collections.sort(neighbors);

            if (neighbors.isEmpty()) {
                System.out.println("None");
            } else {
                for (int k = 0; k < neighbors.size(); k++) {
                    System.out.print(neighbors.get(k) + (k == neighbors.size() - 1 ? "" : " "));
                }
                System.out.println();
            }
        }
    }
}

import sys

def solve():
    n, m = map(int, sys.stdin.readline().split())

    # 在Python中，邻接表通常用字典或列表的列表实现更自然。
    # 这里为了演示链式前向星模板，我们用数组模拟。
    # 对于实际应用，`adj = [[] for _ in range(n + 1)]` 更为Pythonic。
    head = [-1] * (n + 1)
    # 预分配足够大的空间，M条无向边需要2M条有向边
    to_edge = [0] * (m * 2)
    next_edge = [0] * (m * 2)
    edge_idx = 0

    def add(u, v):
        nonlocal edge_idx
        to_edge[edge_idx] = v
        next_edge[edge_idx] = head[u]
        head[u] = edge_idx
        edge_idx += 1

    for _ in range(m):
        u, v = map(int, sys.stdin.readline().split())
        add(u, v)
        add(v, u)

    for i in range(1, n + 1):
        neighbors = []
        j = head[i]
        while j != -1:
            neighbors.append(to_edge[j])
            j = next_edge[j]
        
        neighbors.sort()
        
        if not neighbors:
            print("None")
        else:
            print(*neighbors)

solve()

算法及复杂度

算法：链式前向星存储图，遍历并排序邻接点。
时间复杂度： $\mathcal{O}(M + \sum_{i=1}^{N} \text{deg}(i) \log(\text{deg}(i)))$ 。
- 建图的时间复杂度为 $\mathcal{O}(M)$ 。
- 遍历所有节点的邻接表总共需要 $\mathcal{O}(N+M)$ 的时间。
- 主要的时间开销在于对每个节点的邻接表进行排序。 $\text{deg}(i)$ 是节点 $i$ 的度数。总和 $\sum \text{deg}(i) = 2M$ 。因此，排序的总时间复杂度较为复杂，一个宽松的上界是 $\mathcal{O}(M \log N)$ 。
空间复杂度： $\mathcal{O}(N+M)$ 。
- head 数组需要 $\mathcal{O}(N)$ 的空间。
- 存储边的 edge 数组（或Java/Python中的等效数组）需要 $\mathcal{O}(M)$ 的空间。