Topological Sort | BFS | DFS | Short and Easy to Understand C++ Code
It can be easily observed that the problem can be solved independently for rows and columns. First we can find the row number for each number from 1 to K and th
It can be easily observed that the problem can be solved independently for rows and columns. First we can find the row number for each number from 1 to K and then find the column number for each of them. \nHere, If we see the problem as a graph problem where we have nodes from 1 to K and edges as the dependencies given in **rowConditions** and **colConditions**.  \nthen, after building the graph, we can see that there are a lot od dependencies like 2 should come before 3 and 3 should code after 5 and so on. So How can we find the order which can satisify these conditions. For this, we will use topological sort.\n\nSteps:\n1. Build the graph using **rowConditions**\n2. Find topological sorting order for this graph\n3. Build one more graph using **colConditions**\n4. Find topological sorting order for this graph\n5. fill the matrix using the sorting order given by topological sort. \n\n```\nclass Solution {\npublic:\n    \n    \n    \n    // return false if the graph formed is cyclic in nature. \n    //normal graph building and topological sort code\n    bool buildGraph(vector<vector<int> >& arr, int n, vector<int>& data) {\n        vector<int> adj[n + 1];\n        vector<int> indeg(n + 1, 0);\n        for(auto& curr: arr) {\n            adj[curr[0]].push_back(curr[1]);\n            indeg[curr[1]]++;\n        }\n        queue<int> q;\n        for(int i = 1; i <= n; i++) {\n            if(indeg[i] == 0) {\n                q.push(i);\n            }\n        }\n        while(!q.empty()) {\n            int node = q.front();\n            q.pop();\n            data.push_back(node);\n            for(auto& x: adj[node]) {\n                if(--indeg[x] == 0) {\n                    q.push(x);\n                }\n            }\n        }\n        return data.size() == n;\n    }\n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n        vector<int> topoRow, topoCol;\n        \n        // if the graph formed by the two arrays is cyclic, then answer is not possible.\n        if(!buildGraph(rowConditions, k, topoRow) || !buildGraph(colConditions, k, topoCol)) {\n            return {};\n        }\n        \n        int row[k + 1], col[k + 1];\n    \n        \n        for(int i = 0; i < k; i++) {\n            row[topoRow[i]] = i;\n            col[topoCol[i]] = i;\n        }\n        \n        vector<vector<int> > arr(k, vector<int>(k, 0));\n        for(int i = 1; i <= k; i++) {\n            arr[row[i]][col[i]] = i;\n        }\n        return arr;\n        \n    }\n};\n```\n
['Depth-First Search', 'Breadth-First Search', 'Graph', 'Topological Sort', 'C']