树是一种特殊的图，树没有环且相互连通

图分为有向图和无向图，无向图可以转化为双向的有向图

图的存储

这里介绍一种存储图的方式：邻接表

数组模拟：

int h[N], e[N], ne[N], idx;

把图的每个顶点都开一条单链表，记录在 h[N] 中，这个顶点能连通到的其他点就存储在这个链表里面

e[N] 存储的是能够连通的点，ne[N] 存储的是下一个节点的位置，作用是连通整个链表，使我们能够访问数据

idx 则记录我们当前使用到了哪个空节点

使用vector ：

vector<int> node

直接对每个节点都开一个vector

添加有向图的一条边：

数组模拟：add 函数，在单链表的头节点后插入节点

void add(int a, int b){
    e[idx] = b, ne[b] = h[a], h[a] = idx++;
}

第一步将当前空节点的值 e[idx] 设置为我们 a点 能连通到的 b点 ，然后把 b点 的下一个节点指向原来 h[a]头节点指向的位置

最后把头节点指向我们 add 的空节点，idx++ 移动到下一个空节点

使用vector：

void add(int a, int b) {
    node[a].push_back(b);
}

同理，添加无向图的一条边时，我们只需要 add(a, b)和 add(b, a) 即可

图的遍历

搜索每个点时，只能搜索一次这个点，保证路径不重复
使用 st[N] 来记录每个节点的状态（是否搜索过）

int st[N];

DFS深度优先遍历：

每次都递归搜索当前节点，如果这个节点没有能连通的节点，或能连通的节点已经被搜索过了，则返回

以洛谷B3862为例：

数组模拟：

void dfs(int x,int now) {
    ans = max(ans, now);
    st[now] = 1;
    for (int i = h[now]; i != -1; i = ne[i]) {//从这个节点的链表头开始，一直遍历到空节点
        if (!st[e[i]]) //e[i]为当前可连通到的点
            dfs(x, e[i]);
    }
}

使用vector：

void dfs(int x, int now) {//x为当前考虑的节点，now为当前走到的节点
    ans = max(ans, now);//重置答案
    st[now] = 1;//将搜索过的点标记
    if (node[now].empty()) return;//如果当前走到的节点没有可连通的节点，于是返回
    for (int i = 0; i < node[now].size(); i++)//遍历当前走到的节点可连通的节点
        if (!st[node[now][i]]) dfs(x, node[now][i]);//如果可连通的节点没有被搜索过，就走到它
}

BFS广度优先搜索：拓扑排序

每次只向下搜索一步，将走到的节点放进队列，队列为空时，判断加入队列的点数是否为总节点数，如果不相同说明存在环
我们进行拓扑排序时，需要记录每个点的入度，即有多少条边可以走到这个节点（节点的入度为 $0$ ，则它的拓扑序为局部最高）

以洛谷B3644为例：

记录每个点的入度：

int d[N];
add(x, y);//x能走到y节点，添加一条x指向y的单向边
d[y]++;//y节点的入度加1

数组模拟：

void topsort(void) {
    for (int i = 1; i <= n; i++)
        if (!d[i])
            q.push(i);
    while (!q.empty())
    {
        int tt = q.front();//取出队头元素
        printf("%d ", tt);//输出拓扑序
        q.pop();//弹出队头元素
        for (int i = h[tt]; i != -1; i = ne[i]) {
            d[e[i]]--;
            if (d[e[i]] == 0)
                q.push(e[i]);//将入度为0的点放进队列
        }
    }
}

使用vector：

void topsort(void) {
    for (int i = 1; i <= n; i++)
        if (!d[i])
            q.push(i);
    while (!q.empty())
    {
        int tt = q.front();
        printf("%d ", tt);
        q.pop();
        for (int i = 0; i < node[tt].size(); i++) {
            d[node[tt][i]]--;
            if (d[node[tt][i]] == 0)
                q.push(node[tt][i]);
        }
    }
}