使用vector<vector<int>>存图越界，改用vector[N]正常的原因

问题背景 #

实现简单拓扑排序程序时，尝试用vector<vector<int>>存储图结构，读取图时出现数组越界错误；改用vector<int> edge[N]后程序运行正常。即便尝试初始化edge或把它声明为局部变量，前者仍存在越界问题，需要明确两种存储方式的差异及错误原因。

正确代码 #

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

using i64 = long long;

int n, m;
const int N = 1e6 + 10;
vector<int> edge[N];
int adj[N];
int q[N];

inline void toposort() {
    int front = 1, rear = 0;
    for (int i = 1; i <= n; ++i) {
        if (adj[i] == 0){
            q[++rear] = i;
        }
    }
    while (front <= rear) {
        int s = q[front];
        ++front;
        for (auto c : edge[s]) {
            if (--adj[c] == 0) {
                q[++rear] = c;
            }
        }
    }
    if (rear == n) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

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

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        cin >> x >> y;
        edge[x].push_back(y);
        ++adj[y];
    }

    toposort();

    return 0;
}

错误代码 #

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

using i64 = long long;

int n, m;
const int N = 1e6 + 10;
vector< vector<int> > edge;
int adj[N];
int q[N];

inline void toposort() {
    int front = 1, rear = 0;
    for (int i = 1; i <= n; ++i) {
        if (adj[i] == 0){
            q[++rear] = i;
        }
    }
    while (front <= rear) {
        int s = q[front];
        ++front;
        for (auto c : edge[s]) {
            if (--adj[c] == 0) {
                q[++rear] = c;
            }
        }
    }
    if (rear == n) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

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

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        cin >> x >> y;
        edge[x].push_back(y);
        ++adj[y];
    }

    toposort();

    return 0;
}

测试输入 #

4 4
1 2
2 3
3 4
1 4

差异分析与错误原因 #

1. 两种存储结构的本质区别 #

• vector<int> edge[N]：这是一个固定长度的全局数组，数组元素是vector<int>。因为N是预定义的常量（1e6+10），程序启动时就会分配好N个空vector的存储空间，下标范围覆盖0到N-1。测试输入中节点编号最大为4，远小于N，所以访问edge[x]不会触发越界。
• vector<vector<int>> edge：这是一个动态二维vector，默认初始化后size为0，没有任何可用的下标。当代码中直接访问edge[x]（比如x=1）时，当前edge的有效下标范围是空的，直接触发数组越界错误。

2. 错误代码的修复方式 #

在错误代码的main函数中，读取n和m之后，需要先初始化edge的大小，确保能覆盖所有节点的编号：

cin >> n >> m;
edge.resize(n + 1); // 节点编号从1到n，resize到n+1避免下标越界

这样edge会被初始化为包含n+1个空vector<int>的容器，访问edge[1]到edge[n]就属于合法操作。

3. 为什么初始化/局部变量无法解决问题 #

如果只是声明局部的vector<vector<int>> edge，或者执行无意义的初始化（比如edge = vector<vector<int>>()），都不会改变它size=0的状态，访问edge[x]依然会越界。必须通过resize明确设置容器的大小，才能让下标访问合法。

内容的提问来源于stack exchange，提问作者等不到的时间