拓扑排序

$O(n+m)$

数组写法

const int N = 1e5 + 10;
vector<int>edge[N + 1];
int n, m, q[N + 1], d[N + 1];//d记录了每个点一开始的入度
inline void TopoSort() {
    int front = 1, rear = 0;
    for (int i = 1; i <= n; i++) {
        if (!d[i]) q[++rear] = i;
    }
    while (front <= rear) {
        int x = q[front];
        ++front;
        for (auto y : edge[x]) {
            if (--d[y] == 0)
                q[++rear] = y;
        }
    }
    if (rear == n) printf("YES\n");//此时q中记录了一个合法的拓扑序列
    else printf("NO\n");
}

vector写法

vector<int>edge[maxn];
int n, m, l[maxn], d[maxn];//d记录了每个点一开始的入度，l记录最终的拓扑序列
queue<int>q;
inline void TopoSort() {
    q.push(0);
    int tot = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        if(x) l[++tot] = x;
        for(auto y : edge[x]) {
            if (--d[y] == 0)
                q.push(y);
        }
    }
    if (tot == n)
        printf("Yes\n");
    else
        printf("No\n");
}

字典序最小/最大的拓扑序列

时间复杂度$O(nlogn+m)$

vector<int>edge[10010];
int n, m, l[10010], d[10010];//d记录了每个点一开始的入度，l记录最终的拓扑序列
priority_queue<int, vector<int>, greater<int> >q;//q存放入度为零的点
inline void TopoSort() {
    for (int i = 1; i <= n; i++) {
        if (!d[i]) q.push(i);
    }
    int tot = 0;
    while (!q.empty()) {
        int x = q.top();
        q.pop();
        l[++tot] = x;
        for (auto y : edge[x]) {
            if (--d[y] == 0)
                q.push(y);
        }
    }
    for (int i = 1; i <= tot; i++)
        printf("%d ", l[i]);
}
void solve() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        edge[x].push_back(y);
        d[y]++;
    }
    TopoSort();
}