leetcode

0 class Solution {

1 static vector<int> create(int k, const vector<vector<int>> &conditions) {

2 vector<vector<int>> adj(k + 1);

3 static int count[402];

4

5 memset(count, 0x00, sizeof(count));

6 for (const auto &row : conditions) {

7 adj[row[0]].push_back(row[1]);

8 count[row[1]]++;

9 }

10

11 queue<int> q;

12 for (int i = 1; i <= k; i++) {

13 if (count[i] != 0) continue;

14 q.push(i);

15 }

16

17 if (q.empty()) return {};

18

19 int cnt = 0;

20 vector<int> res(k + 1, -1);

21 while (!q.empty()) {

22 const auto crnt = q.front();

23 q.pop();

24

25 for (const int below : adj[crnt]) {

26 if (--count[below] != 0) continue;

27 q.push(below);

28 }

29

30 res[crnt] = cnt++;

31 }

32

33 return cnt == k ? res : vector<int>();

34 }

35

36 public:

37 vector<vector<int>> buildMatrix(int k, const vector<vector<int>> &rowConditions,

38 const vector<vector<int>> &colConditions) const {

39 const auto row = create(k, rowConditions);

40 if (row.empty()) return {};

41

42 const auto col = create(k, colConditions);

43 if (col.empty()) return {};

44

45 vector<vector<int>> res(k, vector(k, 0));

46 for (int i = 1; i <= k; i++)

47 res[row[i]][col[i]] = i;

48

49 return res;

50 }

51 };