文字教学

这道题是图的DFS和BFS遍历，核心是按“优先访问小编号节点”的规则输出遍历结果：

1. 建图与排序：用邻接表存储有向图，对每个节点的邻接表按升序排序，保证每次先访问小编号。
2. DFS遍历：用栈模拟递归（避免n=1e5时递归栈溢出），弹出节点时标记访问并记录结果，将邻接节点逆序压栈（利用栈LIFO特性保证先访问小编号）。
3. BFS遍历：用队列实现，按邻接表顺序入队，保证先访问小编号。

代码

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

const int N = 1e5 + 10;
vector<int> adj[N];
bool vis[N];
vector<int> dfs_res, bfs_res;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
    }
    // 对每个节点的邻接表排序，保证先访问小编号
    for (int i = 1; i <= n; ++i) {
        sort(adj[i].begin(), adj[i].end());
    }
    
    // DFS遍历（非递归，用栈）
    stack<int> st;
    st.push(1);
    while (!st.empty()) {
        int u = st.top();
        st.pop();
        if (vis[u]) continue;
        vis[u] = true;
        dfs_res.push_back(u);
        // 逆序压入邻接节点，保证出栈顺序是升序
        for (int i = adj[u].size() - 1; i >= 0; --i) {
            int v = adj[u][i];
            if (!vis[v]) st.push(v);
        }
    }
    
    // 重置vis数组，准备BFS
    memset(vis, 0, sizeof(vis));
    // BFS遍历
    queue<int> q;
    q.push(1);
    vis[1] = true;
    bfs_res.push_back(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (!vis[v]) {
                vis[v] = true;
                bfs_res.push_back(v);
                q.push(v);
            }
        }
    }
    
    // 输出结果
    for (int x : dfs_res) cout << x << " ";
    cout << "\n";
    for (int x : bfs_res) cout << x << " ";
    cout << "\n";
    return 0;
}