[C++ with explanation] Simple Topological Sort Implementation
Overview\nThis problem was a standard Topological Sort problem. THANKYOU Leetcode for covering such concept after a long time! \n\nHow I figured it out as Topol
**Overview**\nThis problem was a standard **Topological Sort** problem. THANKYOU Leetcode for covering such concept after a long time! \n\n**How I figured it out as Topological Sort?**\n* Ordering of numbers were required column wise and row wise.\n* Ordering were given in pairs `a -> b`, which means `a` should come before `b`. Looks like Directed Graph.\n\n**Pre-requisite:**\n* Knowledge of Topological Sort in Directed Acyclic Graph (DAG).\n* The resources I used were:\n\t* \t[First Video](https://www.youtube.com/watch?v=qQvylVxCgB4&list=PL5DyztRVgtRVLwNWS7Rpp4qzVVHJalt22&index=26)\n\t* \t[Second Video](https://www.youtube.com/watch?v=eJEpWBieUy4&list=PL5DyztRVgtRVLwNWS7Rpp4qzVVHJalt22&index=27)\n\t* \tThe above video is from [CodeNCode](https://www.youtube.com/channel/UCrR5BJxc1vZ0fmn0MOpuXQQ) Youtube Channel. You can look out his channel for the legendary Graph series (The best I could find).\n\t\n**Algorithm**\n1. Form Directed Graphs out of the orderings in `rowConditions` and `colConditions`\n2. Check these graphs for Acyclicity.  If any of the graphs is cyclic, ordering is not possible. Hence, return `[]`.\n3. Now, we are confirmed that the graphs are DAG. Form topological sorts for the  `rowConditions` and `colConditions`\n4. Let the topological sort from `rowConditions` be `rowSort` and that from `colConditions` be `colSort`.\n5. `rowSort` will determine the position of the element row-wise. \n6. `colSort` will determine the position of the element col-wise. \n\n**Code**\n```\nclass Solution {\n    \n    /* 1. Checking if cycle is present - If YES, Topological Sort is not possible */\n    vector<char> color;\n    bool dfs(int v, vector<vector<int>>& graph) {\n        color[v] = 1;\n        for (int u : graph[v]) {\n            if (color[u] == 0) {\n                if (dfs(u, graph))\n                    return true;\n            } else if (color[u] == 1) {\n                return true;\n            }\n        }\n        color[v] = 2;\n        return false;\n    }\n    bool find_cycle(vector<vector<int>>& graph, int n) {\n        color.assign(n, 0);\n\n        for (int v = 0; v < n; v++) {\n            if (color[v] == 0 && dfs(v, graph))\n                return true;\n        }\n        return false;\n    }\n\n    /* 2. Forming the Topological Sort for DAG */\n    vector<bool> visited;\n    void dfs2(int v, vector<vector<int>>& graph, vector<int>& ans) {\n        visited[v] = true;\n        for (int u : graph[v]) {\n            if (!visited[u])\n                dfs2(u, graph, ans);\n        }\n        ans.push_back(v);\n    }\n\n    void topological_sort(vector<vector<int>>& graph, int n, vector<int>& ans) {\n        visited.assign(n, false);\n        ans.clear();\n        for (int i = 0; i < n; ++i) {\n            if (!visited[i])\n                dfs2(i, graph, ans);\n        }\n        reverse(ans.begin(), ans.end());\n    }\n    \npublic:\n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n        vector<vector<int>> graph1(k);\n        vector<vector<int>> graph2(k);\n        \n        for(auto x:rowConditions) {\n            graph1[x[0] - 1].push_back(x[1] - 1);\n        }\n        for(auto x:colConditions) {\n            graph2[x[0] - 1].push_back(x[1] - 1);\n        }\n        \n        /* 3. Check if CYCLE present in any of the graphs */\n        if(find_cycle(graph1, k) || find_cycle(graph2, k)) return vector<vector<int>>();\n        \n        /* 4. Forming Topological Sort for the DAGs */\n        vector<int> ans1; vector<int> ans2;\n        \n        topological_sort(graph1, k, ans1);\n        topological_sort(graph2, k, ans2);\n        \n        /* 5. Forming the answer from the rowPosition and colPosition for each element */\n        vector<vector<int>> ans(k, vector<int>(k));\n        \n        map<int, int> m;\n        for(int i = 0; i < k; i++) {\n            m[ans2[i]] = i;\n        }\n        \n        for(int i = 0; i < k; i++) {\n            ans[i][m[ans1[i]]] = ans1[i] + 1;\n        }\n        \n        return ans;\n    }\n};\n```\n**Comments:**\n1. For faster implementation, I used the codes available from https://cp-algorithms.com/\n2. Codes are as follows: [Checking cycle in Directed Graph](https://cp-algorithms.com/graph/finding-cycle.html) and [Topological Sort](https://cp-algorithms.com/graph/topological-sort.html)
['Graph', 'Topological Sort', 'C']