Example: DFS-based Algorithm for Topological Sort in C++

// DFS-based Algorithm for Topological Sort
#include <iostream>
#include <vector>
#include <stack> // For storing the result in correct order
#include <map>   // For visited and recursion stack

using namespace std;

// Recursive DFS helper function for topological sort
void dfsTopologicalSort(int u, const vector<vector<int>>& adj, 
                        map<int, bool>& visited, map<int, bool>& recursionStack, 
                        stack<int>& resultStack, bool& hasCycle) {
    visited[u] = true;
    recursionStack[u] = true; // Mark as part of current recursion path

    for (int v : adj[u]) {
        if (hasCycle) return; // If a cycle is detected, stop further processing

        if (!visited[v]) {
            dfsTopologicalSort(v, adj, visited, recursionStack, resultStack, hasCycle);
        } else if (recursionStack[v]) {
            // If 'v' is visited and is in the current recursion stack, it's a back edge -> cycle detected
            hasCycle = true;
            return;
        }
    }

    recursionStack[u] = false; // Remove from current recursion path
    resultStack.push(u);       // Add node to the stack after all its dependencies are processed
}

// Function to perform DFS-based topological sort
vector<int> topologicalSortDFS(int numNodes, const vector<vector<int>>& adj) {
    map<int, bool> visited;
    map<int, bool> recursionStack; // To detect cycles
    stack<int> resultStack;       // Stores the topological order in reverse
    bool hasCycle = false;

    // Initialize visited and recursionStack for all nodes
    for (int i = 0; i < numNodes; ++i) {
        visited[i] = false;
        recursionStack[i] = false;
    }

    // Call DFS for all unvisited nodes
    for (int i = 0; i < numNodes; ++i) {
        if (!visited[i]) {
            dfsTopologicalSort(i, adj, visited, recursionStack, resultStack, hasCycle);
            if (hasCycle) {
                // Return empty vector to indicate a cycle
                return {}; 
            }
        }
    }

    // Pop elements from the stack to get the correct topological order
    vector<int> result;
    while (!resultStack.empty()) {
        result.push_back(resultStack.top());
        resultStack.pop();
    }
    return result;
}

int main() {
    // Example Graph (0->1, 0->2, 1->3, 2->3)
    // Nodes: 0, 1, 2, 3
    int numNodes = 4;
    vector<vector<int>> adj(numNodes);
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(3);

    cout << "Topological Sort using DFS-based Algorithm:" << endl;
    vector<int> sortedOrder = topologicalSortDFS(numNodes, adj);

    if (sortedOrder.empty() && numNodes > 0) {
        cout << "Graph contains a cycle, topological sort not possible." << endl;
    } else {
        for (int node : sortedOrder) {
            cout << node << " ";
        }
        cout << endl;
    }

    // Another Example Graph (5->0, 4->0, 5->2, 4->1, 2->3, 3->1)
    // Nodes: 0, 1, 2, 3, 4, 5
    numNodes = 6;
    adj.assign(numNodes, vector<int>()); // Clear and resize
    adj[5].push_back(0);
    adj[5].push_back(2);
    adj[4].push_back(0);
    adj[4].push_back(1);
    adj[2].push_back(3);
    adj[3].push_back(1);
    
    cout << "\nTopological Sort using DFS-based Algorithm (Another Example):" << endl;
    sortedOrder = topologicalSortDFS(numNodes, adj);

    if (sortedOrder.empty() && numNodes > 0) {
        cout << "Graph contains a cycle, topological sort not possible." << endl;
    } else {
        for (int node : sortedOrder) {
            cout << node << " ";
        }
        cout << endl;
    }

    // Example with a cycle: 0->1, 1->2, 2->0
    numNodes = 3;
    adj.assign(numNodes, vector<int>());
    adj[0].push_back(1);
    adj[1].push_back(2);
    adj[2].push_back(0);

    cout << "\nTopological Sort using DFS-based Algorithm (Cycle Example):" << endl;
    sortedOrder = topologicalSortDFS(numNodes, adj);

    if (sortedOrder.empty() && numNodes > 0) {
        cout << "Graph contains a cycle, topological sort not possible." << endl;
    } else {
        for (int node : sortedOrder) {
            cout << node << " ";
        }
        cout << endl;
    }

    return 0;
}