aboutsummaryrefslogtreecommitdiff
path: root/build_matrix_conditions.cpp
blob: e192ddaf8a9d1c19001d4470bcacbc2035687123 (plain)
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// 2392. Build a Matrix With Conditions
#include "leetcode.h"

/*
 * you are givne a positive integer 'k'. you are also given a 2d integer array
 * 'rowConditions' of size 'n' where 'rowConditions[i] = [above_i, below_i]' and
 * a 2d integer array 'colConditions' of size 'm' where 'colConditions[i] =
 * [left_i, right_i]'. the two arrays contain integers from 1 to 'k'. you have
 * to build a 'k * k' matrix that contains each of the numbers from 1 to 'k'
 * exactly once. the remaining cells should satisfy the following conditions.
 * the number 'above_i' should appear in a row that is strictly above the row at
 * which the number 'below_i' appears for all 'i'. the number 'left_i' should
 * appear in a column that is strictly left of the column at which the number
 * 'right_i' appears for all 'i'. return any matrix that satisfies these
 * conditions.
 */

class Solution {
private:
  vector<char> colour;
  vector<bool> visited;
  bool dfs(int v, vector<vector<int>> &graph) {
    colour[v] = 1;
    for (int i : graph[v]) {
      if (!colour[i]) {
        if (dfs(i, graph))
          return true;
      } else if (colour[i] == 1)
        return true;
    }
    colour[v] = 2;
    return false;
  }
  bool find_cycle(vector<vector<int>> &graph, int n) {
    colour.assign(n, 0);
    for (int i = 0; i < n; i++)
      if (!colour[i] && dfs(i, graph))
        return true;
    return false;
  }
  void dfs2(int v, vector<vector<int>> &graph, vector<int> &res) {
    visited[v] = true;
    for (int i : graph[v])
      if (!visited[i])
        dfs2(i, graph, res);
    res.push_back(v);
  }
  void topo_sort(vector<vector<int>> &graph, int n, vector<int> &res) {
    visited.assign(n, false);
    res.clear();
    for (int i = 0; i < n; ++i)
      if (!visited[i])
        dfs2(i, graph, res);
    reverse(res.begin(), res.end());
  }

public:
  vector<vector<int>> buildMatrix(int k, vector<vector<int>> &rowConditions,
                                  vector<vector<int>> &colConditions) {
    vector<vector<int>> g1(k), g2(k);
    for (auto i : rowConditions)
      g1[i[0] - 1].push_back(i[1] - 1);
    for (auto i : colConditions)
      g2[i[0] - 1].push_back(i[1] - 1);
    if (find_cycle(g1, k) || find_cycle(g2, k))
      return vector<vector<int>>();
    vector<int> a1, a2;
    topo_sort(g1, k, a1);
    topo_sort(g1, k, a2);
    vector<vector<int>> ans(k, vector<int>(k));
    map<int, int> m;
    for (int i = 0; i < k; i++)
      m[a2[i]] = i;
    for (int i = 0; i < k; i++)
      ans[i][m[a1[i]]] = a1[i] + 1;
    return ans;
  }
};

int main() {
  Solution obj;
  vvd rc1 = {{1, 2}, {3, 2}}, cc1 = {{2, 1}, {3, 2}};
  vvd rc2 = {{1, 2}, {2, 3}, {3, 1}, {2, 3}}, cc2 = {{2, 1}};
  vvd bm1 = obj.buildMatrix(3, rc1, cc1),
           bm2 = obj.buildMatrix(3, rc2, cc2);
  for (int i = 0; i < bm1.size(); i++) {
    for (int j = 0; j < bm1[0].size(); j++)
      printf("%d ", bm1[i][j]);
    printf("\n");
  }
  printf("\n");
  for (int i = 0; i < bm2.size(); i++) {
    for (int j = 0; j < bm2[0].size(); j++)
      printf("%d ", bm2[i][j]);
    printf("\n");
  }
  printf("\n");
}