Graph theory: topological sorting

A topological sort

For directed acyclic graphs （DAG） A linear sort of vertices of , Each vertex in the sort sequence will appear and only appear once , And for all directed edges u→v, After finishing the sequence u All in v front .

In topological ordering , We use it L Record the topological sequence so far , Using set S Record all absence L The penetration in is 0 The summit of ;

First, traverse the vertices of the whole graph , If the penetration of a vertex is 0, Add it to S;

When S Isn't empty ：

stay S Take any vertex in x, take x Add to L At the end of the team , And put x from S Delete from ;

Ergodic x The departure side x→y, Delete this edge , If y It becomes 0, Then add it to S in ;

At the end of the loop , If all points are added L, Then we find a legal topological sequence , Otherwise, it can be proved that there are rings in the graph ;

queue L、S It's usually used The same queue Realization

Time complexity ：$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;
}

Dictionary order is the smallest / The largest topological sort

Only need to maintain S The data structure of is changed into a heap （ Priority queue 、Set）, Then select the smallest from the heap each time / Largest element x To operate .

Time complexity ：$O(nlongn+m)$

Dictionary order is the smallest

priority_queue How to write it

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 How to write it

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;
}

Dictionary order maximum

priority_queue How to write it

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 How to write it

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;
}