#include <bits/stdc++.h>
using namespace std;
struct ArcNode{
    int adjvex;
    ArcNode* next;
};
struct VertexNode{
    int vertex;
    ArcNode* firstedge;
};
class ALGraph
{
public:
    ALGraph(int n, int e);
    ~ALGraph(){};
    void BFSTraverse(int v);
    void DFSTraverse(int v);
private:
    int vertexNum,arcNum;
    VertexNode* adjlist = new VertexNode[vertexNum + 1];
    int* visited = new int[vertexNum + 1];

};
ALGraph::ALGraph(int n, int e)
{
    int x, y;
    vertexNum = n; arcNum = e;
    for(int i = 1; i <= vertexNum; i++)
    {
        adjlist[i].vertex = i;
        adjlist[i].firstedge = NULL;
        visited[i] = 0;
    }
    for(int i = 1; i <= arcNum; i++)
    {
        ArcNode* t;
        ArcNode* p = new ArcNode;
        cin >> x >> y;
        p->adjvex= y;
        t = adjlist[x].firstedge;
        if(t == NULL)
        {
            p->next = adjlist[x].firstedge;
            adjlist[x].firstedge = p;
            continue;
        }
        while(t != NULL)
        {
            if(t->next != NULL && t->next->adjvex > p->adjvex && t->adjvex < p->adjvex || t->next == NULL)
            {
                p->next = t->next;
                t->next = p;
                break;
            }else if(t->adjvex > p->adjvex)
            {
                p->next = adjlist[x].firstedge;
                adjlist[x].firstedge = p;
                break;
            }
            t = t->next;
        }
    }
}
void ALGraph::DFSTraverse(int v)
{
    int k = v;
    ArcNode* p;
    p = adjlist[k].firstedge;
    cout << adjlist[k].vertex << " ";
    visited[k] = 1;
    while(p != NULL)
    {
        k = p->adjvex;
        if(visited[k] == 0)DFSTraverse(k);
        p = p->next;
    }
}
void ALGraph::BFSTraverse(int v)
{
    for(int i = 1; i <= vertexNum; i++)visited[i] = 0;
    queue<int> Q;
    Q.push(v);
    cout << v << " ";
    visited[v] = 1;
    while(!Q.empty())
    {
        v = Q.front();
        Q.pop();
        ArcNode* p;
        p = adjlist[v].firstedge;
        while(p != NULL)
        {
            int j = p->adjvex;
            if(visited[j] == 0)
            {
                cout << adjlist[j].vertex << " ";
                visited[j] = 1;
                Q.push(j);
            }
            p = p->next;
        }
    }
}
int main()
{
    int n, e;
    cin >> n >> e;
    ALGraph grh(n, e);
    grh.DFSTraverse(1);
    cout << endl;
    grh.BFSTraverse(1);
    return 0;
}

呜，全部RE，明明几乎照着书上写的