拓扑排序

给定一张有向无环图，将所有顶点排序，排序后的序列 $A$ 满足：对于图中的每条有向边 $(u,v)$，$u$ 在 $A$ 中的位置比 $v$ 在 $A$ 中的位置小，即 $u$ 在 $v$ 之前出现。则称 $A$ 为该图的顶点的一个拓扑序列。

如下图的一个拓扑序列是：$2\to 8\to 0\to 3\to 7\to 1\to 5\to 6\to 9\to 4\to 11\to 10\to 12$。

拓扑序列不唯一！

Kahn 算法

设 $e[u]$ 存 $u$ 的所有邻点，$t$ 存拓扑序列，$din[u]$ 存点 $u$ 的入度。

Kahn 的算法核心是用队列维护一个入度为 $0$ 的顶点集合。

算法步骤：

1. 初始时，队列 $q$ 压入所有入度为 $0$ 的顶点。
2. 每次从 $q$ 弹出一个顶点 $u$，将 $u$ 加入 $t$，并将 $u$ 的所有邻点的入度减 $1$，即删除 $u$ 的所有出边。
3. 若 $u$ 的邻点 $v$ 的入度变为 $0$，则将 $v$ 压入 $q$。
4. 重复步骤 2 到 3，直到 $q$ 为空。

Kahn 算法的时间复杂度是 $O(V+E)$，其中 $V$ 是顶点数，$E$ 是边数。

vector<int> e[MAXN], t;
int din[MAXN];

void Kahn() {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (!din[i]) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        t.push_back(u);
        for (int v : e[u]) {
            din[v]--;
            if (!din[v]) {
                q.push(v);
            }
        }
    }

    if (t.size() == n) {
        for (int i = 0; i < n; i++) {
            cout << t[i] << " ";
        }
    } else {
        cout << "图中存在环" << endl;
    }
}

DFS 算法

设 $e[u]$ 存 $u$ 的所有邻点，$t$ 存拓扑序列，$c[u]$ 存点 $u$ 的颜色。

$c[u]=\{-1,0,1\}$，表示 $u$ 初次访问、未访问、已回溯。

DFS 的算法核心是变色，搜索的过程中给节点进行染色，如果存在拓扑序列，则每个节点的颜色都会经历 $0\to -1\to 1$ 的过程。

算法步骤：

1. 初始时每个节点都为 $0$，即未访问。
2. 枚举每个节点 $u$ ，执行 DFS，进入节点 $u$ 时，将 $u$ 的颜色置为 $-1$，然后枚举 $u$ 的邻点 $v$，如果 $v$ 的颜色为 $0$，说明 $v$ 尚未访问，则递归进入 $v$。
3. 如果枚举完 $u$ 的所有邻点后，没有发现环，则 $u$ 的颜色置为 $1$，并将 $u$ 加入 $t$。
4. 如果发现 $u$ 的某一邻点 $v$ 的颜色为 $-1$，说明回到了祖先节点，则说明存在环，则停止搜索，一路返回 false，退出程序。

DFS 算法的时间复杂度是 $O(V+E)$，其中 $V$ 是顶点数，$E$ 是边数。

vector<int> e[MAXN], t;
int c[MAXN];

bool DFS(int u) {
    c[u] = -1;
    for (int v : e[u]) {
        if (c[v] == -1) return false;
        else if (c[v] == 0) {
            if (!DFS(v)) return false;
        }
    }
    c[u] = 1;
    t.push_back(u);
    return true;
}

void topoSort() {
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= n; i++) {
        if (c[i] == 0) {
            if (!DFS(i)) {
                cout << "图中存在环" << endl;
                return;
            }
        }
    }
    reverse(t.begin(), t.end());
    for (int i = 0; i < n; i++) {
        cout << t[i] << " ";
    }
}

思考：如何求字典序最大/最小的拓扑序列？