用C语言编写程序对给定的有向图（不一定连通）进行深度优先遍历，图中包含n个顶点，编号为0至n-1。本题限定在深度优先遍历过程中，如果同时出现多个待访问的顶点，则优先选择编号最小的一个进行访问，以顶点0为遍历起点。 输入格式: 输入第一行为两个整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过50。接下来e行表示每条边的信息，每行为两个整数a、b，表示该边的端点编号，但各边并非按端点编号顺序排列。 输出格式: 输出为一行整数，每个整数后一个空格，即该有向图的深度优先遍历结点序列。 输入样例1: 3 3 0 1 1 2 0 2 输出样例1: 0 1 2 输入样例2: 4 4 0 2 0 1 1 2 3 0 输出样例2: 0 1 2 3

以下是 C 语言代码实现：

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 20000

int n, e;
int h[MAX_N], e[MAX_N], ne[MAX_N], idx;
int dfn[MAX_N], low[MAX_N], timestamp;
int stack[MAX_N], top;
int in_stack[MAX_N], scc_cnt, sccno[MAX_N];

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

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stack[ ++ top] = u, in_stack[u] = 1;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = low[u] < low[j] ? low[u] : low[j];
        }
        else if (in_stack[j])
            low[u] = low[u] < dfn[j] ? low[u] : dfn[j];
    }

    if (dfn[u] == low[u])
    {
        ++ scc_cnt;
        int y;
        do {
            y = stack[top --];
            in_stack[y] = 0;
            sccno[y] = scc_cnt;
        } while (y != u);
    }
}

int main()
{
    scanf("%d%d", &n, &e);
    for (int i = 0; i < n; i ++) h[i] = -1;
    for (int i = 0; i < e; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    tarjan(0);

    for (int i = 0; i < n; i ++)
        printf("%d ", sccno[i]);

    return 0;
}

在这里，我使用了 Tarjan 算法来解决这个问题。

首先，对于给定的有向图进行深度优先遍历并不是很好做，因为有向图中存在环。

而 Tarjan 算法恰好可以将有向图转化为 DAG，使得遍历更加简单。

做法是：使