#include <bits/stdc++.h>
using namespace std;
// 链式前向星

char data[] = "ABCD";
struct Edge {
    // int w;
    int to;
    int nxt;
};

const int M = 10000;
const int N = 100;
Edge e[M]; // 数组链表 
int head[N]; // head[1] 顶点编号为1的链表头索引（数组索引） 
int cnt;

void addEdge(int u, int v) // , int w
{
    e[++cnt].to = v; // cnt是新分配的节点的索引号 

    // head[u] 头插法
    e[cnt].nxt = head[u];
    head[u] = cnt;
}

// addEdge2
void add_undirected_edge(int u, int v)
{
    addEdge(u, v);
    addEdge(v, u);
}

bool vis[N];
void dfs(int u)
{
    cout << data[u] << ' ';
    vis[u] = true;
    // head[u] 这条链表中 
    for (int i = head[u]; i != 0; i = e[i].nxt)
    {
        // int v = e[i].to;
        if (!vis[e[i].to])
            dfs(e[i].to);
    }
}

bool inq[N];
void bfs(int u)
{
    queue<int> q;
    q.push(u);
    inq[u] = true;

    while (!q.empty())
    {
        int u1 = q.front();
        q.pop();
        cout << data[u1] << ' ';
        // head[u1]链表
        for (int i = head[u1]; i != 0; i = e[i].nxt)
        {
            if (!inq[e[i].to])
            {
                q.push(e[i].to);
                inq[e[i].to] = true;
            }
        }

    }
}

int main()
{
    // 构建图
    addEdge(0, 1); 
    addEdge(0, 3); 

    addEdge(1, 0); 
    addEdge(1, 2);
    addEdge(1, 3);

    addEdge(2, 1);
    addEdge(2, 3);   

    addEdge(3, 0);    
    addEdge(3, 1); 
    addEdge(3, 2);

    // 打印邻接表
    for (int u = 0; u < 4; u ++)
    {
        cout << u << "->";
        // 遍历head[u]的链表
        for (int i = head[u]; i != 0; i = e[i].nxt)
        {
            cout << e[i].to << ' ';
        }
        cout << endl;
    }

    dfs(0); // A D C B

    cout << endl;
    bfs(0); // A D B C

    return 0;
} 

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

char data[] = "ABCD";
const int N = 1000;
// vector<int> g[N]; // 邻接表

/*
struct Edge {
    int to;
    int w;
};

list<Edge> g[N];
*/

list<int> g[N]; // 等价于链式前向星  STL中的链表

void addEdge(int u, int v)
{
    g[u].push_back(v);
} 

bool vis[N];
void dfs(int u)
{
    cout << data[u] << ' ';
    vis[u] = true;
    // g[u] list中
    for (auto it = g[u].begin(); it != g[u].end(); it ++)
    {
        if (!vis[*it])
            dfs(*it);    
    } 
}

void bfs(int u)
{

}

int main()
{
    // 构建图
    addEdge(0, 1); 
    addEdge(0, 3); 

    addEdge(1, 0); 
    addEdge(1, 2);
    addEdge(1, 3);

    addEdge(2, 1);
    addEdge(2, 3);   

    addEdge(3, 0);    
    addEdge(3, 1); 
    addEdge(3, 2);

    // 打印邻接表
    for (int u = 0; u < 4; u ++)
    {
        cout << u << "->";
        // g[u] list链表
        for (auto it = g[u].begin(); it != g[u].end(); it ++)
        {
            cout << *it << ' ';
        }
        cout << endl;
    }

    dfs(0); // A B C D 

    return 0;
}