GeeksForGeeks-Problem/2392. Build a Matrix With Conditions at 9ebfd7886b3bee5cd6a09f66f19c181f32012ed8 · Michael-Calce/GeeksForGeeks-Problem · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public:

    bool toposort(vector<vector<int>> &adj, vector<int> &tsort, vector<int> &ind)
    {
        int V = ind.size();
        queue<int> q;

        for(int i=0 ; i<V ; i++) if(ind[i] == 0) q.push(i);

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

            for(auto &v: adj[u])
            {
                ind[v] -= 1;
                if(ind[v] == 0) q.push(v);
            }
        }

        if(tsort.size() != V) return false;
        return true;
    }
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {

        vector<vector<int>> adj_row(k, vector<int> ());
        vector<vector<int>> adj_col(k, vector<int> ());

        vector<int> ind_row(k, 0);
        vector<int> ind_col(k, 0);

        for(auto &edge: rowConditions)
        {
            adj_row[edge[0]-1].push_back(edge[1]-1);
            ind_row[edge[1]-1] += 1;
        }

        for(auto &edge: colConditions)
        {
            adj_col[edge[0]-1].push_back(edge[1]-1);
            ind_col[edge[1]-1] += 1;
        }

        vector<int> tsort_row;
        vector<int> tsort_col;

        bool notCycle_row = toposort(adj_row, tsort_row, ind_row);
        bool notCycle_col = toposort(adj_col, tsort_col, ind_col);

        if(!notCycle_row || !notCycle_col) return {};
        vector<vector<int>> ans(k, vector<int> (k, 0));

        for(int row = 0 ; row < k ; row++)
        {
            int col = find(tsort_col.begin(), tsort_col.end(), tsort_row[row]) - tsort_col.begin();
            ans[row][col] = tsort_row[row]+1;
        }

        return ans;
    }
};