Flower Planting With No Adjacent LeetCode solution in C++

1
class Solution {
2
 public:
3
  int check(vector<int> a[], vector<int> &col, int sv, int i) {
4
    for (auto it : a[sv]) {
5
      if (col[it] == i) return 0;
6
    }
7
    return 1;
8
  }
9

10
  void dfs(vector<int> a[], vector<int> &col, int sv, int lc) {
11
    for (int i = 1; i < 5; i++) {
12
      if (check(a, col, sv, i)) {
13
        col[sv] = i;
14
        break;
15
      }
16
    }
17
    for (auto it : a[sv]) {
18
      if (col[it] == -1) {
19
        dfs(a, col, it, col[sv]);
20
      }
21
    }
22
  }
23
  vector<int> gardenNoAdj(int n, vector<vector<int>> &paths) {
24
    vector<int> a[n];
25
    for (auto it : paths) {
26
      a[it[0] - 1].push_back(it[1] - 1);
27
      a[it[1] - 1].push_back(it[0] - 1);
28
    }
29

30
    vector<int> col(n, -1);
31
    for (int i = 0; i < n; i++) {
32
      if (col[i] == -1) {
33
        dfs(a, col, i, -7);
34
      }
35
    }
36
    return col;
37
  }
38
};