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

char data[] = {'A', 'B', 'C', 'D'};

vector<int> g[4]; // 邻接表实现 

bool vis[4];
void dfs(int u)
{
    cout << data[u] << ' ';
    vis[u] = true;

    // dfs u的邻接点
    // g[u] vector中
    for (int j = 0; j < g[u].size(); j ++)
    {
        int v = g[u][j];
        if (!vis[v])
            dfs(v);
        /* 
        if (!vis[g[u][j]])
            dfs(g[u][j]);
        */
    } 

}

bool inq[4];
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] << ' ';
        // g[u1]
        for (int j = 0; j < g[u1].size(); j ++)
        {
            // int v = g[u1][j];
            if (!inq[g[u1][j]])
            {
                q.push(g[u1][j]);
                inq[g[u1][j]] = true;
            }
        }
    }
}

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

int main()
{

    // 构建图 
    g[0].push_back(1);
    g[0].push_back(3);

    g[1].push_back(0);
    g[1].push_back(2);
    g[1].push_back(3);

    g[2].push_back(1);
    g[2].push_back(3);

    g[3].push_back(0);
    g[3].push_back(1);
    g[3].push_back(2);

    // 打印邻接表 
    for (int i = 0; i < 4; i ++)
    {
        // g[i]
        cout << i << "->";
        for (int j = 0; j < g[i].size(); j ++)
            cout << g[i][j] << ' ';
        cout << endl;
    }

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

    bfs(0);  // A B D C

    return 0;
} 

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

char data[] = {'A', 'B', 'C', 'D'};

// 链表节点 
// 边节点 EdgeNode Node 
// 以边为核心 
struct Edge {
    int to; // 边的终点 指向的节点编号，邻接点编号u -> v 代表的是v 
    // int w;
    int nxt; // 指向下一个Edge节点 
};

const int M = 1000;
Edge e[M];
int cnt = 1; // 分配链表节点空间 
int head[N]; // 节点的链表头数组, head[1] 代表节点编号1的链表头索引（指针） 

// 构建u的（邻接表）链表 - 头插法 
// 只增加一条边 
void addEdge(int u, int v)
{
    int cur = cnt++; // 给v节点分配空间
    e[cur].to = v;

    // 链接到u的链表中，头插法
    e[cur].nxt = head[u];
    head[u] = cur;
}

void dfs(int u)
{

}

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);

    // 打印邻接表（链表） 

    return 0;
}