图论：拓扑排序

拓扑排序

对于有向无环图（DAG）的顶点进行的一种线性排序，排序序列中每个顶点都会且仅会出现一次，且对于所有的有向边u→v，排完序后u都在v前面。

在拓扑排序中，我们用L记录到目前为止拓扑序列，用集合S记录所有不在L中的入度为0的顶点；

首先遍历整张图上的顶点，如果一个顶点的入度为0，将它加入S；

当S不为空时：

在S中任取一个顶点x，将x加入到L的队尾，并把x从S中删去；

遍历从x出发的边x→y，把这条边删掉，如果y的入度变成了0，则将其加入到S中；

循环结束时，如果所有的点都加入了L，那么我们就找到了一个合法的拓扑序列，否则可以证明图中存在环；

队列L、S一般用同一个队列实现

时间复杂度：$O(n+m)$

vector<int> edge[N];
int n, m, d[N];
queue<int> q;
inline bool TopoSort()
{
    int tot = 0;
    for (int i = 1; i <= n; i++)
        if (!d[i])
            q.push(i);
    while (!q.empty())
    {
        int x = q.front();
        ++tot;
        q.pop();
        for (auto y : edge[x])
            if (--d[y] == 0)
                q.push(y);
    }
    if (tot == n)
        return true;
    else
        return false;
}

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

只需要将维护S的数据结构改成堆（优先队列、Set），然后每次从堆中选出最小/最大的元素x进行操作。

时间复杂度：$O(nlongn+m)$

字典序最小

priority_queue写法

vector<int> edge[N];
int n, m, d[N], l[N];
priority_queue<int, vector<int>, greater<int>> q;
inline bool TopoSort()
{
    int tot = 0;
    for (int i = 1; i <= n; i++)
        if (!d[i])
            q.push(i);

    while (!q.empty())
    {
        int x = q.top();
        q.pop();
        l[++tot] = x;
        for (auto y : edge[x])
            if (--d[y] == 0)
                q.push(y);
    }
    if (tot == n)
        return true;
    else
        return false;
}

set写法

vector<int> edge[N];
int n, m, d[N], l[N];
set<int> q;
inline bool TopoSort()
{
    int tot = 0;
    for (int i = 1; i <= n; i++)
        if (!d[i])
            q.insert(i);
    while (!q.empty())
    {
        int x = *q.begin();
        q.erase(x);
        l[++tot] = x;
        for (auto y : edge[x])
            if (--d[y] == 0)
                q.insert(y);
    }
    if (tot == n)
        return true;
    else
        return false;
}

字典序最大

priority_queue写法

vector<int> edge[N];
int n, m, d[N], l[N];
priority_queue<int> q;
inline bool TopoSort()
{
    int tot = 0;
    for (int i = 1; i <= n; i++)
        if (!d[i])
            q.push(i);

    while (!q.empty())
    {
        int x = q.top();
        q.pop();
        l[++tot] = x;
        for (auto y : edge[x])
            if (--d[y] == 0)
                q.push(y);
    }
    if (tot == n)
        return true;
    else
        return false;
}

set写法

vector<int> edge[N];
int n, m, d[N], l[N];
set<int> q;
inline bool TopoSort()
{
    int tot = 0;
    for (int i = 1; i <= n; i++)
        if (!d[i])
            q.insert(i);
    while (!q.empty())
    {
        int x = *q.rbegin();  // int x = *(--q.end());
        q.erase(x);
        l[++tot] = x;
        for (auto y : edge[x])
            if (--d[y] == 0)
                q.insert(y);
    }
    if (tot == n)
        return true;
    else
        return false;
}