#include <iostream>
#include <vector>   // for std::vector
#include <stack>    // for std::stack
#include <queue>    // for std::queue

class Graph {
    int V;
    int E;
    int** adj;

public:
    Graph(int v_size, int e_size) {
        V = v_size;
        E = e_size;

        adj = new int*[v_size];
        for (int row = 0; row < V; ++row) {
            adj[row] = new int[V];
            for (int col = 0; col < V; ++col) {
                adj[row][col] = 0;
            }
        }
    }

    void addEdge(int first, int second) {
        adj[first - 1][second - 1] = 1;
    }

    void DFS(int start, std::vector<bool>& visited) {
        std::cout << start << ' ';
        visited[start] = true;

        for (int i = 0; i < V; ++i) {

            if (adj[start][i] == 1 && (!visited[i])) {
                DFS(i, visited);
            }
        }
    }

    void print_matrix() {
        for (int row = 0; row < V; ++row) {
            for (int col = 0; col < V; ++col) {
                std::cout << adj[row][col] << ' ';
            }
            std::cout << '\n';
        }
    }

    void topological_sort_util_dfs(int v, std::vector<bool> &visited, std::stack<int>& stack) {
        visited[v] = true;

        for (int i = 0; i < V; ++i) {
            if (adj[v][i] == 1 && (!visited[i])) {
                topological_sort_util_dfs(i, visited, stack);
            }
        }

        // Vertex from 0 to V-size
        stack.push(v + 1);
    }

    void topological_sort_DFS() {
        std::stack<int> stack;
        std::vector<bool> visited(V, false);

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

        while (!stack.empty()) {
            std::cout << stack.top() << ' ';
            stack.pop();
        }
        std::cout << '\n';
    }

    void topological_sort_del() {
        // Create a vector to store indegrees of all vertices
        std::vector<int> in_degree(V, 0);

        for (int row = 0; row < V; ++row) {
            for (int col = 0; col < V; col++) {
                if (adj[row][col] == 1) {
                    ++in_degree[col];
                }
            }
        }

        // Create an queue and enqueue all vertices with indegree 0
        std::queue<int> queue;
        for (int vertex = 0; vertex < V; ++vertex) {
            if (in_degree[vertex] == 0) {
                queue.push(vertex);
            }
        }

        int count_visisted_vertices = 0;
        std::vector<int> top_order;

        while (!queue.empty()) {
            int vertex = queue.front();
            queue.pop();
            top_order.push_back(vertex);

            // Iterate through the neibhbours and decrease their in-degree
            for (int j = 0; j < V; ++j) {
                if (adj[vertex][j]) {
                    --in_degree[j];

                    if (in_degree[j] == 0) {
                        queue.push(j);
                    }
                }
            }

            ++count_visisted_vertices;
        }

        if (count_visisted_vertices != V) {
            std::cout << "There is a cycle in the graph." << '\n';
            std::cout << "Can't do topological sort." << '\n';
            return;
        }

        for (const auto& vertex : top_order) {
            std::cout << vertex + 1 << ' ';
        }
        std::cout << '\n';
    }
};

int main()
{
    int v = 10;
    int e = 20;

    Graph G(v, e);
    /*
    G.addEdge(1, 4);
    G.addEdge(1, 6);
    G.addEdge(2, 4);
    G.addEdge(2, 5);
    G.addEdge(3, 5);
    G.addEdge(3, 8);
    G.addEdge(4, 6);
    G.addEdge(4, 7);
    G.addEdge(5, 7);
    G.addEdge(5, 8);
    */
    G.addEdge(5, 2);
    G.addEdge(5, 7);
    G.addEdge(1, 2);
    G.addEdge(7, 8);
    G.addEdge(6, 9);
    G.addEdge(7, 6);
    G.addEdge(7, 9);
    G.addEdge(2, 3);
    G.addEdge(10, 6);
    G.addEdge(3, 4);
    G.addEdge(10, 5);
    G.addEdge(2, 7);
    G.addEdge(1, 10);
    G.addEdge(8, 4);
    G.addEdge(8, 6);
    G.addEdge(8, 9);

    G.print_matrix();

    G.topological_sort_DFS();
    G.topological_sort_del();

    return 0;
}