Topological sorting & critical path

1、 A topological sort

Definition ：  To a Directed acyclic graph (Directed Acyclic Graph abbreviation DAG) G Topological sort , Yes, it will G All the vertices in are arranged in a linear sequence , Make any pair of vertices in the graph u and v, Ruobian <u,v>∈E(G), be u In a linear sequence v Before .

Next is Yang Yang. Get up and arrive 9#504 The process , Can you write a topological sequence belonging to the Yang Yang wake up process

In the right order ： open one 's eyes -> shirt -> socks -> coat -> shoes -> Out of the door （ Is not the only ） 

        The topological sequence ：   V1 -> V6 -> V3 -> V4 -> V2 -> V5 （ Is not the only ）

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int d[N], q[N], e[N], ne[N], h[N], idx;
int n, m;

void add (int a, int b)   //  Adjacency table edge storage 
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool topsort ()
{
    int hh = 0, tt = -1;
    
    for (int i = 1; i <= n; i ++) 
        if (!d[i]) q[++ tt] = i;    //  First of all, let's set the degree of penetration as 0  Into the queue 
    
    while (hh <= tt)   //  Array mock queue 
    {
        int t = q[hh ++];
        
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0)  //  Traverse all connected points at this point ,  If the penetration is zero after removing this point ,  You can continue to deposit 
                q[++ tt] = j;
        }
    }
    return tt == n - 1;   //  In the queue, you can ensure that all are topologically sorted ,  If the number is n individual ,  It shows that topological sorting can be formed 
}

int main ()
{
    cin >> n >> m;
    memset (h, -1, sizeof h);
    
    while (m --)
    {
        int a, b;
        cin >> a >> b;
        add (a, b);
        d[b] ++;   //  The degree of ++   
    }
    
    if (!topsort()) puts("-1");
    else for (int i = 0; i < n; i ++) cout << q[i] << " ";   //  The elements in the queue happen to be topological sorting sequence 
    return 0;
}

Topic link -ACwing-- problem-164

Code ：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e4 + 10;
vector<int> q[N];// Adjacency table mapping 
int a, b;
int l, r;
map<pair<int, int>, int> mp;// Remove duplicate edges when entering 
struct node
{
    int x;
    int j;
};
int arr[N];

bitset<30001> dis[30001];// There are several before the save path 
queue<node> p;
void t()// Topological sorting function 
{
    while (!p.empty())
    {
        node temp = p.front();// Take the lead 
        p.pop();
        int len = q[temp.x].size();
        for (int i = 0; i < len; i++)
        {
            arr[q[temp.x][i]]--;// One less entry 
            dis[q[temp.x][i]] |= dis[temp.x];// Number of nodes updated to this point 
            if (arr[q[temp.x][i]] == 0)// The degree of 0 Join the queue 
            {
                int tem = dis[q[temp.x][i]].count();
                p.push({q[temp.x][i], tem});// Can't be dis[q[temp.x][i]].count() Just put it in , Will report a mistake , Give first tem
            }
        }
    }
    return;
}
signed main()
{

    cin >> a >> b;
    for (int i = 1; i <= a; i++)
    {
        dis[i][i] = 1;
    }
    for (int i = 0; i < b; i++)
    {
        scanf("%d%d", &l, &r);
        q[r].push_back(l);// Reverse penetration , Push backward 
        if (mp[{r, l}] != 1)// Repetition points do not increase penetration 
        {
            arr[l]++;
        }
        mp[{r, l}] = 1;
    }
    for (int i = 1; i <= a; i++)
    {
        sort(q[i].begin(), q[i].end());// Sort 
        q[i].erase(unique(q[i].begin(), q[i].end()), q[i].end());// Only after sorting can we use this method to duplicate edges 
    }

    for (int i = 1; i <= a; i++)
    {
        if (arr[i] == 0)// Enter zero and join , Join multiple times , It's OK to join once , Put the function outside 
        {
            p.push({i, 1});
            t();// function , A topological sort 
        }
    }

    for (int i = 1; i <= a; i++)
    {
        cout << dis[i].count() << endl;
    }

    return 0;
}

2、 critical path

  The longest road problem ：    Topic link SDUTACM -problem-2498

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
 
const int N = 10010, M = 50010;
 
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];
int r[N], C[N];
int path[N];  //  Record it father
int npath[N];  //  Record the number of this path ,  Process dictionary order 
int s, en; //  starting point end point 
vector<int> a;
 
void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a]++, w[idx] = -1 * c, h[a] = idx++;  //  The longest path problem is transformed into the shortest path problem with negative weight  spfa
}
 
int spfa(int x) {
    // ios;
    memset(dist, 0x3f, sizeof dist);
 
    dist[x] = 0;
    queue<int> q;
    q.push(x);
    st[x] = true;
 
    while (q.size()) {
        int t = q.front();
        q.pop();
 
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
 
            if (dist[j] > dist[t] + w[i] ||
                dist[j] == dist[t] + w[i] && (npath[j] == npath[t] + 1 && path[j] > j || j > t)) {  //  Take the one with smaller dictionary order 
                path[j] = t;
                npath[j] = npath[t] + 1;
                dist[j] = dist[t] + w[i];
                if (!st[j]) q.push(j), st[j] = true;
            }
        }
    }
    return dist[en];
}
 
int main() {
    int n, m;
    ios;
    while (cin >> n >> m) {
        idx = 0;
        memset(st, 0, sizeof st);
        memset(path, 0, sizeof path);
        memset(C, 0, sizeof C);
        memset (npath, 0, sizeof npath);
        memset(r, 0, sizeof r);
        a.clear();
        memset(h, -1, sizeof h);
        while (m--) {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c);
            r[b]++;  //  The degree of 
            C[a] ++; //  The degree of 
        }
 
        for (int i = 1; i <= n; i++)
            if (!r[i])
                s = i;
            else if (!C[i])
                en = i;
 
        int res = -1 * spfa(s);
 
        cout << res << endl;
        while (path[en]) {    //  Pop up path 
            a.push_back(en);
            a.push_back(path[en]);
            en = path[en];
        }
        int x = 1;
        for (int i = a.size() - 1; i >= 0; i--) {
            if (x % 2 != 0)
                cout << a[i] << " ";     //  Output format 
            else
                cout << a[i] << '\n';
            x++;
        }
    }
    return 0;
}