为了方便你快速构建 OJ 测试数据，我编写了一个高效的 C++ 数据生成器。它能够自动生成 10 组涵盖各种边界情况（如链状图、星形图、完全不连通图等）的测试点，并同步生成标准答案。

数据生成器设计逻辑：

1. 拓扑结构设计：
   • 连通图：通过随机树或长链确保从 0 号房间出发可以到达所有房间。
   • 非连通图：人为截断路径，或者将房间分为两个互不往来的集合。
2. 约束处理：严格遵守 $N \le 1000$ 和钥匙总数 $\le 3000$ 的限制。
3. 求解器：内置基于 BFS 的非递归求解逻辑，确保 .out 文件准确。
4. 随机性：使用 std::mt19937 引擎，保证数据的随机分布质量。

数据生成器源码 (C++14)

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <random>
#include <string>
#include <algorithm>
#include <set>

using namespace std;

// ---------------- 核心算法：用于生成标准答案 (.out) ----------------
bool solve(int n, const vector<vector<int>>& adj) {
    vector<bool> vis(n, false);
    queue<int> q;
    
    q.push(0);
    vis[0] = true;
    int count = 1;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : adj[u]) {
            if (!vis[v]) {
                vis[v] = true;
                count++;
                q.push(v);
            }
        }
    }
    return count == n;
}

// ---------------- 辅助工具：写入文件 ----------------
void write_case(int t, int n, const vector<vector<int>>& adj) {
    string in_name = to_string(t) + ".in";
    string out_name = to_string(t) + ".out";
    
    // 写入 .in 文件
    ofstream fin(in_name);
    fin << n << "\n";
    for (int i = 0; i < n; ++i) {
        fin << adj[i].size();
        for (int key : adj[i]) {
            fin << " " << key;
        }
        fin << "\n";
    }
    fin.close();
    
    // 写入 .out 文件
    ofstream fout(out_name);
    fout << (solve(n, adj) ? "true" : "false") << endl;
    fout.close();
    
    cout << "Testcase " << t << " finished (n=" << n << ")." << endl;
}

// ---------------- 随机数工具 ----------------
mt19937 rng(1337);
int randInt(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

// ---------------- 各类场景生成逻辑 ----------------
void generate() {
    for (int t = 1; t <= 10; ++t) {
        int n = 1000;
        vector<vector<int>> adj(n);
        int key_limit = 3000;
        int current_keys = 0;

        auto add_key = [&](int u, int v) {
            if (current_keys < key_limit) {
                adj[u].push_back(v);
                current_keys++;
                return true;
            }
            return false;
        };

        if (t == 1) { // 极小边界情况：连通
            n = 2; adj.assign(n, vector<int>());
            add_key(0, 1);
        }
        else if (t == 2) { // 极小边界情况：不连通
            n = 2; adj.assign(n, vector<int>());
            // 0 号房没钥匙
        }
        else if (t == 3) { // 极限长链：1000个房间 (True)
            for (int i = 0; i < n - 1; ++i) add_key(i, i + 1);
        }
        else if (t == 4) { // 极限星形：0号房有所有钥匙 (True)
            for (int i = 1; i < n; ++i) add_key(0, i);
        }
        else if (t == 5) { // 截断长链：在最后一步断开 (False)
            for (int i = 0; i < n - 2; ++i) add_key(i, i + 1);
        }
        else if (t == 6) { // 环形结构 (True)
            for (int i = 0; i < n; ++i) add_key(i, (i + 1) % n);
        }
        else if (t == 7) { // 两个完全孤立的集合 0-499, 500-999 (False)
            for (int i = 0; i < 498; ++i) add_key(i, i + 1);
            for (int i = 500; i < 998; ++i) add_key(i, i + 1);
        }
        else if (t == 8) { // 随机连通图 (True)
            vector<int> nodes(n);
            for(int i=0; i<n; ++i) nodes[i] = i;
            shuffle(nodes.begin() + 1, nodes.end(), rng);
            // 确保连通性：每个点连向后面的某个点
            for (int i = 0; i < n - 1; ++i) {
                add_key(nodes[i], nodes[i + 1]);
            }
            // 补充随机钥匙
            while (current_keys < 2500) {
                add_key(randInt(0, n - 1), randInt(0, n - 1));
            }
        }
        else if (t == 9) { // 包含大量冗余钥匙和自环 (True)
            for (int i = 1; i < n; ++i) add_key(i-1, i);
            for (int i = 0; i < 1000; ++i) add_key(randInt(0, n-1), randInt(0, n-1));
        }
        else { // 复杂非连通：看起来很密，但漏掉了几个关键房间 (False)
            for (int i = 0; i < n; ++i) {
                if (i == 500) continue; // 没人有 500 的钥匙
                int target = randInt(0, n - 1);
                if (target != 500) add_key(i, target);
            }
            // 确保 0 能走到大部分地方，除了 500 及其下游
            for (int i = 0; i < 499; ++i) add_key(i, i + 1);
        }

        write_case(t, n, adj);
    }
}

int main() {
    generate();
    return 0;
}

测试点说明：

生成器使用建议：

1. 文件大小：由于 $N=1000$，每个输入文件大小约为 $10 \sim 20\text{ KB}$。10 个测试点总计不到 $200\text{ KB}$，远低于 $2\text{ MB}$ 限制。
2. 安全性：求解器 solve 使用 std::queue 实现 BFS，属于非递归写法，不会因为图的深度过大（如长链）而导致生成器爆栈。
3. 零除处理：代码中没有除法运算，且随机范围 randInt(0, n-1) 保证了索引合法。
4. 编译建议：使用 g++ gen.cpp -o gen -std=c++14 -O2 编译后直接运行即可。它会在当前目录产生 1.in 至 10.out。

在 NOI 竞赛中，图论的连通性判定主要通过深度优先搜索 (DFS) 或 广度优先搜索 (BFS) 实现。由于本题 $N \le 1000$，属于较小规模，核心在于代码的准确性和对图存储结构的理解。

版本一：深度优先搜索 (DFS) 递归版

思路：这是最符合竞赛直觉的写法。利用递归模拟进入房间的过程，使用 vis 数组记录已进入的房间，避免死循环。

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 1005;
vector<int> adj[MAXN]; // 邻接表存储图
bool vis[MAXN];       // 标记数组，记录房间是否被访问过
int cnt = 0;          // 统计访问到的房间总数

// DFS 函数：代表进入编号为 u 的房间
void dfs(int u) {
    vis[u] = true;
    cnt++; // 每进入一个新房间，计数加1
    
    // 遍历当前房间里的所有钥匙
    for (int v : adj[u]) {
        if (!vis[v]) { // 如果钥匙指向的房间没去过
            dfs(v);    // 前往该房间
        }
    }
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    
    // 读入每个房间的钥匙情况
    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        while (k--) {
            int key;
            cin >> key;
            adj[i].push_back(key); // 建立一条从 i 到 key 的有向边
        }
    }

    // 从 0 号房间开始搜索
    dfs(0);

    // 判断访问到的房间数是否等于总房间数
    if (cnt == n) cout << "true" << endl;
    else cout << "false" << endl;

    return 0;
}

版本二：广度优先搜索 (BFS) 迭代版

思路：使用队列模拟“包里装钥匙”的过程。这种方法在处理大规模数据（如 $N > 10^5$）时比递归 DFS 更安全，因为不会导致系统栈溢出。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 1005;
vector<int> adj[MAXN];
bool vis[MAXN];

int main() {
    int n;
    if (!(cin >> n)) return 0;

    for (int i = 0; i < n; i++) {
        int k; cin >> k;
        while (k--) {
            int key; cin >> key;
            adj[i].push_back(key);
        }
    }

    queue<int> q;
    q.push(0);      // 初始进入 0 号房
    vis[0] = true;
    int visited_count = 1;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) {
            if (!vis[v]) {
                vis[v] = true;
                visited_count++;
                q.push(v);
            }
        }
    }

    if (visited_count == n) cout << "true" << endl;
    else cout << "false" << endl;

    return 0;
}

版本三：竞赛极致优化版（链式前向星 + 静态队列）

思路：在 NOI 提高组或省选中，为了应对极大规模数据（$N, E \ge 10^6$），选手常使用链式前向星代替 vector，并用手写静态队列代替 std::queue 以压减常数时间。

#include <cstdio>
#include <cstring>

const int MAXN = 1005;
const int MAXE = 3005; // 钥匙总数即为边数

// 链式前向星存储结构
int head[MAXN], to[MAXE], nxt[MAXE], edge_cnt;
bool vis[MAXN];
int q[MAXN]; // 手写静态队列

void add_edge(int u, int v) {
    to[++edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

int main() {
    int n;
    if (scanf("%d", &n) == EOF) return 0;

    for (int i = 0; i < n; i++) {
        int k;
        scanf("%d", &k);
        for (int j = 0; j < k; j++) {
            int target;
            scanf("%d", &target);
            add_edge(i, target);
        }
    }

    // BFS 过程
    int l = 0, r = 0;
    q[r++] = 0;
    vis[0] = true;
    int ans = 1;

    while (l < r) {
        int u = q[l++];
        // 遍历链式前向星
        for (int i = head[u]; i; i = nxt[i]) {
            int v = to[i];
            if (!vis[v]) {
                vis[v] = true;
                ans++;
                q[r++] = v;
            }
        }
    }

    if (ans == n) printf("true\n");
    else printf("false\n");

    return 0;
}

复杂度分析思考过程

1. 时间复杂度分析：

   • 构建图：读入所有钥匙并存储。复杂度正比于钥匙总数 $E$。
   • 遍历图：在 DFS/BFS 中，每个房间（节点）最多入队/递归一次，每把钥匙（边）最多被扫描一次。
   • 总复杂度：$O(N + E)$。对于 $N=1000, E=3000$，计算量在万级，远低于竞赛 1s 运行 $10^8$ 次的要求。

2. 空间复杂度分析：

   • 存储图：邻接表或链式前向星占用 $O(N + E)$。
   • 辅助空间：标记数组 $O(N)$，递归栈或队列 $O(N)$。
   • 总复杂度：$O(N + E)$。内存占用约为几百 KB，远低于竞赛 128MB/256MB 的限制。

时间复杂度优化建议

• 输入输出优化：当数据量达到 $10^5$ 时，cin/cout 会非常慢。建议使用 scanf/printf 或手写 read() 函数（快读）。
• 存储结构：vector<vector<int>> 在频繁扩容时有开销。对于固定边数的图，链式前向星（版本三）是执行效率最高的结构。
• 内存连续性：在 BFS 中使用数组模拟队列比 std::queue 略快，因为它保证了内存的连续性，对 CPU 缓存更友好。

读题关键词与易错点（教练寄语）

1. “0 号房间是解锁的”：这是遍历的唯一起点。
2. “有向图”逻辑：注意钥匙是单向的。A 房间有 B 房间钥匙，不代表你可以从 B 回到 A。
3. 重复钥匙：房间里可能有重复的钥匙，或者钥匙指向已经打开的房间。必须使用 vis 数组过滤，否则会导致死循环或计数错误。
4. $N$ 的范围：如果 $N$ 很大，递归 DFS 可能会“爆栈”。在 NOI 竞赛中，如果遇到深度可能达到 $10^5$ 的图，优先考虑 BFS 或手工模拟栈。