Topological Sort - DP on DAG

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Compute topological order with Kahn's algorithm and then the longest path from a given source.
5
// Works even with negative edge weights because the graph is acyclic.
6
7
int main() {
8
    ios::sync_with_stdio(false);
9
    cin.tie(nullptr);
10
11
    int n, m; // number of vertices and edges
12
    // Example input:
13
    // 6 7
14
    // 1 2 2
15
    // 1 3 1
16
    // 2 4 3
17
    // 2 5 4
18
    // 3 5 2
19
    // 4 6 1
20
    // 5 6 3
21
    // 1
22
    if (!(cin >> n >> m)) {
23
        cerr << "Expected n m on input\n";
24
        return 0;
25
    }
26
27
    struct Edge { int to; long long w; };
28
    vector<vector<Edge>> g(n + 1);
29
    vector<int> indeg(n + 1, 0);
30
    for (int i = 0; i < m; ++i) {
31
        int u, v; long long w; cin >> u >> v >> w;
32
        g[u].push_back({v, w});
33
        indeg[v]++;
34
    }
35
36
    int s; cin >> s; // source vertex
37
38
    // Kahn's algorithm for topological order
39
    queue<int> q;
40
    for (int v = 1; v <= n; ++v) if (indeg[v] == 0) q.push(v);
41
42
    vector<int> topo; topo.reserve(n);
43
    while (!q.empty()) {
44
        int u = q.front(); q.pop();
45
        topo.push_back(u);
46
        for (auto &e : g[u]) {
47
            if (--indeg[e.to] == 0) q.push(e.to);
48
        }
49
    }
50
51
    if ((int)topo.size() != n) {
52
        cout << "The graph is not a DAG (cycle detected)." << '\n';
53
        return 0;
54
    }
55
56
    const long long NEG_INF = (long long)-4e18; // sentinel for unreachable
57
    vector<long long> dist(n + 1, NEG_INF);
58
    dist[s] = 0;
59
60
    // Forward DP in topological order: relax edges from each u
61
    for (int u : topo) {
62
        if (dist[u] == NEG_INF) continue; // unreachable; skip
63
        for (auto &e : g[u]) {
64
            dist[e.to] = max(dist[e.to], dist[u] + e.w);
65
        }
66
    }
67
68
    // Output longest distances from source to every vertex
69
    // Unreachable vertices remain as "-INF"
70
    for (int v = 1; v <= n; ++v) {
71
        if (dist[v] == NEG_INF) cout << "-INF\n";
72
        else cout << dist[v] << '\n';
73
    }
74
75
    return 0;
76
}
77

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Count the number of distinct directed paths from s to t in a DAG using DP in topological order.
5
// Computation is done modulo MOD.
6
7
int main() {
8
    ios::sync_with_stdio(false);
9
    cin.tie(nullptr);
10
11
    const int MOD = 1'000'000'007;
12
13
    int n, m; // vertices and edges
14
    // Example input:
15
    // 5 6
16
    // 1 2
17
    // 1 3
18
    // 2 4
19
    // 3 4
20
    // 2 5
21
    // 4 5
22
    // 1 5
23
    if (!(cin >> n >> m)) return 0;
24
25
    vector<vector<int>> g(n + 1);
26
    vector<int> indeg(n + 1, 0);
27
    for (int i = 0; i < m; ++i) {
28
        int u, v; cin >> u >> v;
29
        g[u].push_back(v);
30
        indeg[v]++;
31
    }
32
    int s, t; cin >> s >> t;
33
34
    // Kahn's algorithm for topological order
35
    queue<int> q;
36
    for (int v = 1; v <= n; ++v) if (indeg[v] == 0) q.push(v);
37
38
    vector<int> topo; topo.reserve(n);
39
    while (!q.empty()) {
40
        int u = q.front(); q.pop();
41
        topo.push_back(u);
42
        for (int v : g[u]) if (--indeg[v] == 0) q.push(v);
43
    }
44
45
    if ((int)topo.size() != n) {
46
        cout << 0 << '\n'; // cycles imply infinite paths; for DAG DP, we treat as zero/invalid
47
        return 0;
48
    }
49
50
    vector<int> ways(n + 1, 0);
51
    ways[s] = 1;
52
53
    // DP: propagate path counts along edges
54
    for (int u : topo) {
55
        if (ways[u] == 0) continue;
56
        for (int v : g[u]) {
57
            ways[v] += ways[u];
58
            if (ways[v] >= MOD) ways[v] -= MOD;
59
        }
60
    }
61
62
    cout << ways[t] % MOD << '\n';
63
    return 0;
64
}
65

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Compute the shortest distance from every vertex to a given sink t in a weighted DAG.
5
// We process vertices in reverse topological order and relax incoming states via outgoing edges.
6
7
int main() {
8
    ios::sync_with_stdio(false);
9
    cin.tie(nullptr);
10
11
    int n, m; // number of vertices and edges
12
    // Example input:
13
    // 6 7
14
    // 1 2 2
15
    // 1 3 1
16
    // 2 4 3
17
    // 2 5 4
18
    // 3 5 2
19
    // 4 6 1
20
    // 5 6 3
21
    // 6
22
    if (!(cin >> n >> m)) return 0;
23
24
    struct Edge { int to; long long w; };
25
    vector<vector<Edge>> g(n + 1);
26
    vector<int> indeg(n + 1, 0);
27
    for (int i = 0; i < m; ++i) {
28
        int u, v; long long w; cin >> u >> v >> w;
29
        g[u].push_back({v, w});
30
        indeg[v]++;
31
    }
32
    int t; cin >> t; // sink vertex
33
34
    // Topological sort (Kahn)
35
    queue<int> q;
36
    for (int v = 1; v <= n; ++v) if (indeg[v] == 0) q.push(v);
37
    vector<int> topo; topo.reserve(n);
38
    while (!q.empty()) {
39
        int u = q.front(); q.pop();
40
        topo.push_back(u);
41
        for (auto &e : g[u]) if (--indeg[e.to] == 0) q.push(e.to);
42
    }
43
    if ((int)topo.size() != n) {
44
        cout << "The graph is not a DAG (cycle detected)." << '\n';
45
        return 0;
46
    }
47
48
    const long long INF = (long long)4e18;
49
    vector<long long> dist(n + 1, INF);
50
    dist[t] = 0; // base case
51
52
    // Process in reverse topological order: from later to earlier
53
    for (int i = (int)topo.size() - 1; i >= 0; --i) {
54
        int u = topo[i];
55
        for (auto &e : g[u]) {
56
            if (dist[e.to] != INF) {
57
                dist[u] = min(dist[u], e.w + dist[e.to]);
58
            }
59
        }
60
    }
61
62
    // Output shortest distances to t (INF means unreachable)
63
    for (int v = 1; v <= n; ++v) {
64
        if (dist[v] == INF) cout << "INF\n";
65
        else cout << dist[v] << '\n';
66
    }
67
68
    return 0;
69
}
70