Untitled

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>

using namespace std;


class Graph {
private:
    int V;  // Number of vertices
    vector<vector<int>> adjList;  
public:
   
    Graph(int V) {
        this->V = V;
        adjList.resize(V);
    }

   
    void addEdge(int u, int v) {
        adjList[u].push_back(v);
    }


    void dfsTopologicalSortUtil(int v, vector<bool>& visited, stack<int>& Stack) {
        visited[v] = true;

      
        for (int i = 0; i < adjList[v].size(); i++) {
            int neighbor = adjList[v][i];
            if (!visited[neighbor]) {
                dfsTopologicalSortUtil(neighbor, visited, Stack);
            }
        }

       
        Stack.push(v);
    }

 
    void dfsTopologicalSort() {
        stack<int> Stack;
        vector<bool> visited(V, false);

        
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                dfsTopologicalSortUtil(i, visited, Stack);
            }
        }

     
        cout << "Topological Sort (DFS-based): ";
        while (!Stack.empty()) {
            cout << Stack.top() << " ";
            Stack.pop();
        }
        cout << endl;
    }

    
    void inDegreeTopologicalSort() {
        vector<int> inDegree(V, 0);
        queue<int> q;

        
        
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < adjList[i].size(); j++) {
                inDegree[adjList[i][j]]++;
            }
        }
        for (int i = 0; i < V; i++) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }

        vector<int> topoOrder;

     
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            topoOrder.push_back(u);

     
            for (int i = 0; i < adjList[u].size(); i++) {
                int v = adjList[u][i];
                if (--inDegree[v] == 0) {
                    q.push(v);
                }
            }
        }

      
        if (topoOrder.size() != V) {
            cout << "The graph contains a cycle, topological sort is not possible!" << endl;
            return;
        }

     
        cout << "Topological Sort (In-degree based): ";
        for (int i = 0; i < topoOrder.size(); i++) {
            cout << topoOrder[i] << " ";
        }
        cout << endl;
    }

 
    void printAdjacencyList() {
        cout << "Adjacency List of the Graph:" << endl;
        for (int i = 0; i < V; i++) {
            cout << i << ": ";
            for (int j = 0; j < adjList[i].size(); j++) {
                cout << adjList[i][j] << " ";
            }
            cout << endl;
        }
    }
};


int main() {
    int V, E;
    cout << "Enter number of vertices: ";
    cin >> V;
    cout << "Enter number of edges: ";
    cin >> E;

    Graph g(V);

    cout << "Enter edges (u v) where there is an edge u -> v:" << endl;
    for (int i = 0; i < E; i++) {
        int u, v;
        cin >> u >> v;
        g.addEdge(u, v);
    }

   
    g.printAdjacencyList();

    
    g.dfsTopologicalSort();


    g.inDegreeTopologicalSort();

    return 0;
}