C++ 在线编译器

main.cpp

ShareResetEraseRun

StdinOptional input fed to the program on stdin - one line per line.2 linesAlice 30

Output

Click Run to see the output here.

#include <iostream>
#include <queue>
#include <vector>

int main() {
    // Directed acyclic graph: adj[u] lists nodes that depend on u
    std::vector<std::vector<int>> adj = {
        {},      // 0
        {},      // 1
        {3},     // 2 -> 3
        {1},     // 3 -> 1
        {0, 1},  // 4 -> 0, 1
        {0, 2},  // 5 -> 0, 2
    };
    int n = static_cast<int>(adj.size());
    std::vector<int> inDegree(n, 0);
    for (const auto& neighbors : adj) {
        for (int v : neighbors) ++inDegree[v];
    }
    // Kahn's algorithm: start from nodes with no incoming edges
    std::queue<int> ready;
    for (int u = 0; u < n; ++u) {
        if (inDegree[u] == 0) ready.push(u);
    }
    std::cout << "Topological order: ";
    while (!ready.empty()) {
        int u = ready.front();
        ready.pop();
        std::cout << u << " ";
        // Removing u unlocks neighbors whose in-degree drops to 0
        for (int v : adj[u]) {
            if (--inDegree[v] == 0) ready.push(v);
        }
    }
    std::cout << "\n";
    return 0;
}