#include <iostream>
#include <vector>
#include <list>
using namespace std;

// Adjacency List Representation
class GraphAdjList {
private:
    int V; // Number of vertices
    vector<list<int>> adj; // Adjacency list
    
public:
    GraphAdjList(int vertices) : V(vertices) {
        adj.resize(V);
    }
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u); // For undirected graph
    }
    
    void printGraph() {
        cout << "Adjacency List Representation:" << endl;
        for (int i = 0; i < V; i++) {
            cout << "Vertex " << i << ": ";
            for (int neighbor : adj[i]) {
                cout << neighbor << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
    
    vector<list<int>>& getAdjList() { return adj; }
    int getVertices() { return V; }
};

// Adjacency Matrix Representation
class GraphAdjMatrix {
private:
    int V;
    vector<vector<int>> adjMatrix;
    
public:
    GraphAdjMatrix(int vertices) : V(vertices) {
        adjMatrix.resize(V, vector<int>(V, 0));
    }
    
    void addEdge(int u, int v) {
        adjMatrix[u][v] = 1;
        adjMatrix[v][u] = 1; // For undirected graph
    }
    
    void printGraph() {
        cout << "Adjacency Matrix Representation:" << endl;
        cout << "   ";
        for (int i = 0; i < V; i++) {
            cout << i << " ";
        }
        cout << endl;
        
        for (int i = 0; i < V; i++) {
            cout << i << ": ";
            for (int j = 0; j < V; j++) {
                cout << adjMatrix[i][j] << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
    
    bool hasEdge(int u, int v) {
        return adjMatrix[u][v] == 1;
    }
    
    vector<vector<int>>& getMatrix() { return adjMatrix; }
    int getVertices() { return V; }
};

int main() {
    // Create graph with 5 vertices
    GraphAdjList graphList(5);
    GraphAdjMatrix graphMatrix(5);
    
    // Add edges: 0-1, 0-4, 1-2, 1-3, 1-4, 2-3, 3-4
    vector<pair<int, int>> edges = {{0,1}, {0,4}, {1,2}, {1,3}, {1,4}, {2,3}, {3,4}};
    
    for (auto edge : edges) {
        graphList.addEdge(edge.first, edge.second);
        graphMatrix.addEdge(edge.first, edge.second);
    }
    
    graphList.printGraph();
    graphMatrix.printGraph();
    
    // Compare space complexity
    cout << "Space Analysis:" << endl;
    cout << "Adjacency List: O(V + E) = O(" << graphList.getVertices() << " + " << edges.size() << ") = O(" << (graphList.getVertices() + edges.size()) << ")" << endl;
    cout << "Adjacency Matrix: O(V²) = O(" << graphMatrix.getVertices() << "²) = O(" << (graphMatrix.getVertices() * graphMatrix.getVertices()) << ")" << endl;
    
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

class DijkstraGraph {
private:
    int V;
    vector<vector<pair<int, int>>> adj; // {neighbor, weight}
    
public:
    DijkstraGraph(int vertices) : V(vertices) {
        adj.resize(V);
    }
    
    void addEdge(int u, int v, int weight) {
        adj[u].push_back({v, weight});
        adj[v].push_back({u, weight}); // For undirected graph
    }
    
    vector<int> dijkstra(int src) {
        // Distance vector initialized to infinity
        vector<int> dist(V, INT_MAX);
        vector<int> parent(V, -1);
        
        // Priority queue: {distance, vertex}
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        
        dist[src] = 0;
        pq.push({0, src});
        
        cout << "Dijkstra's algorithm execution:" << endl;
        cout << "Step | Current | Distance | Neighbors Updated" << endl;
        cout << "-----|---------|----------|------------------" << endl;
        
        int step = 1;
        
        while (!pq.empty()) {
            int currentDist = pq.top().first;
            int u = pq.top().second;
            pq.pop();
            
            // Skip if we've already found a shorter path
            if (currentDist > dist[u]) continue;
            
            cout << " " << step++ << "   |    " << u << "    |    " << currentDist << "     | ";
            
            bool updated = false;
            for (auto& edge : adj[u]) {
                int v = edge.first;
                int weight = edge.second;
                
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    parent[v] = u;
                    pq.push({dist[v], v});
                    cout << v << "(" << dist[v] << ") ";
                    updated = true;
                }
            }
            
            if (!updated) cout << "none";
            cout << endl;
        }
        
        return dist;
    }
    
    void printShortestPaths(int src, const vector<int>& dist) {
        cout << "\nShortest distances from vertex " << src << ":" << endl;
        cout << "Vertex | Distance | Path" << endl;
        cout << "-------|----------|-----" << endl;
        
        for (int i = 0; i < V; i++) {
            cout << "  " << i << "    |    ";
            if (dist[i] == INT_MAX) {
                cout << "∞" << "    | No path" << endl;
            } else {
                cout << dist[i] << "    | ";
                printPath(src, i, dist);
                cout << endl;
            }
        }
    }
    
private:
    void printPath(int src, int dest, const vector<int>& dist) {
        if (src == dest) {
            cout << src;
            return;
        }
        
        // Reconstruct path (simplified version)
        cout << src << " -> ... -> " << dest;
    }
};

// Weighted graph for testing
class WeightedGraphExample {
public:
    static void demonstrateDijkstra() {
        DijkstraGraph g(6);
        
        // Add weighted edges
        g.addEdge(0, 1, 4);
        g.addEdge(0, 2, 2);
        g.addEdge(1, 2, 1);
        g.addEdge(1, 3, 5);
        g.addEdge(2, 3, 8);
        g.addEdge(2, 4, 10);
        g.addEdge(3, 4, 2);
        g.addEdge(3, 5, 6);
        g.addEdge(4, 5, 3);
        
        cout << "Graph edges with weights:" << endl;
        cout << "0-1: 4, 0-2: 2, 1-2: 1, 1-3: 5, 2-3: 8," << endl;
        cout << "2-4: 10, 3-4: 2, 3-5: 6, 4-5: 3" << endl << endl;
        
        vector<int> distances = g.dijkstra(0);
        g.printShortestPaths(0, distances);
    }
};

int main() {
    WeightedGraphExample::demonstrateDijkstra();
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;

class TopologicalSort {
private:
    int V;
    vector<vector<int>> adj;
    vector<string> vertexNames;
    
public:
    TopologicalSort(int vertices) : V(vertices) {
        adj.resize(V);
        vertexNames.resize(V);
    }
    
    void setVertexName(int v, const string& name) {
        vertexNames[v] = name;
    }
    
    void addEdge(int u, int v) {
        adj[u].push_back(v); // Directed edge from u to v
    }
    
    // Kahn's Algorithm for Topological Sort
    vector<int> topologicalSortKahn() {
        vector<int> inDegree(V, 0);
        
        // Calculate in-degrees
        for (int u = 0; u < V; u++) {
            for (int v : adj[u]) {
                inDegree[v]++;
            }
        }
        
        // Queue for vertices with 0 in-degree
        queue<int> q;
        for (int i = 0; i < V; i++) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }
        
        vector<int> topOrder;
        cout << "Kahn's Algorithm execution:" << endl;
        cout << "Step | Removed | Queue Status | In-degrees Updated" << endl;
        cout << "-----|---------|-------------|-------------------" << endl;
        
        int step = 1;
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            topOrder.push_back(u);
            
            cout << " " << step++ << "   |   " << vertexNames[u] << "    | ";
            
            // Reduce in-degree for all neighbors
            for (int v : adj[u]) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    q.push(v);
                }
            }
            
            // Print current queue status
            queue<int> tempQ = q;
            cout << "[";
            bool first = true;
            while (!tempQ.empty()) {
                if (!first) cout << ",";
                cout << vertexNames[tempQ.front()];
                tempQ.pop();
                first = false;
            }
            cout << "] | ";
            
            // Print neighbors updated
            for (int v : adj[u]) {
                cout << vertexNames[v] << "(" << inDegree[v] << ") ";
            }
            cout << endl;
        }
        
        return topOrder;
    }
    
    // DFS-based Topological Sort
    vector<int> topologicalSortDFS() {
        vector<bool> visited(V, false);
        vector<int> topoOrder;
        
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                topologicalSortDFSUtil(i, visited, topoOrder);
            }
        }
        
        // Reverse the order
        reverse(topoOrder.begin(), topoOrder.end());
        return topoOrder;
    }
    
private:
    void topologicalSortDFSUtil(int v, vector<bool>& visited, vector<int>& topoOrder) {
        visited[v] = true;
        
        for (int u : adj[v]) {
            if (!visited[u]) {
                topologicalSortDFSUtil(u, visited, topoOrder);
            }
        }
        
        topoOrder.push_back(v);
    }
    
public:
    void printTopologicalOrder(const vector<int>& topOrder, const string& method) {
        cout << "\nTopological ordering (" << method << "):" << endl;
        for (int i = 0; i < topOrder.size(); i++) {
            cout << vertexNames[topOrder[i]];
            if (i < topOrder.size() - 1) cout << " -> ";
        }
        cout << endl;
    }
    
    bool hasCycle() {
        vector<int> topOrder = topologicalSortKahn();
        return topOrder.size() != V; // If not all vertices are included, there's a cycle
    }
};

// Course scheduling example
class CourseScheduler {
public:
    static void demonstrateTopologicalSort() {
        // Create a course dependency graph
        TopologicalSort courses(8);
        
        // Set course names
        courses.setVertexName(0, "Math");
        courses.setVertexName(1, "Physics");
        courses.setVertexName(2, "Chemistry");
        courses.setVertexName(3, "Biology");
        courses.setVertexName(4, "AdvMath");
        courses.setVertexName(5, "AdvPhys");
        courses.setVertexName(6, "Research");
        courses.setVertexName(7, "Thesis");
        
        // Add prerequisites (dependencies)
        courses.addEdge(0, 4); // Math -> AdvMath
        courses.addEdge(1, 5); // Physics -> AdvPhys
        courses.addEdge(0, 1); // Math -> Physics
        courses.addEdge(2, 3); // Chemistry -> Biology
        courses.addEdge(4, 6); // AdvMath -> Research
        courses.addEdge(5, 6); // AdvPhys -> Research
        courses.addEdge(3, 6); // Biology -> Research
        courses.addEdge(6, 7); // Research -> Thesis
        
        cout << "Course Prerequisites:" << endl;
        cout << "Math -> Physics, AdvMath" << endl;
        cout << "Physics -> AdvPhys" << endl;
        cout << "Chemistry -> Biology" << endl;
        cout << "AdvMath, AdvPhys, Biology -> Research" << endl;
        cout << "Research -> Thesis" << endl << endl;
        
        vector<int> kahnOrder = courses.topologicalSortKahn();
        courses.printTopologicalOrder(kahnOrder, "Kahn's Algorithm");
        
        vector<int> dfsOrder = courses.topologicalSortDFS();
        courses.printTopologicalOrder(dfsOrder, "DFS-based");
    }
};

int main() {
    CourseScheduler::demonstrateTopologicalSort();
    return 0;
}