1042. Flower Planting With No Adjacent

You have n gardens, labeled from 1 to n, and an array paths where paths[i] = [xi, yi] describes a bidirectional path between garden xi to garden yi. In each garden, you want to plant one of 4 types of flowers.

All gardens have at most 3 paths coming into or leaving it.

Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.

Return any such a choice as an array answer, where answer[i] is the type of flower planted in the (i+1)th garden. The flower types are denoted 1, 2, 3, or 4. It is guaranteed an answer exists.

class Solution {
    int getFlower(int n) {
        for(int i = 1; i <= 4; i++) {
            if(!(n & (1<<i))) return i;
        }
        return -1;
    }
public:
    vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
        vector<vector<int>> conn(n);
        vector<int> res(n,0);
        vector<int> near(n,0);
        for(auto p : paths) {
            conn[p[0] - 1].push_back(p[1] - 1);
            conn[p[1] - 1].push_back(p[0] - 1);
        }
        queue<int> q;
        for(int i = 0; i < n; i++) {
            if(res[i] == 0) {
                q.push(i);
                while(!q.empty()) {
                    auto g = q.front(); q.pop();
                    int flower = getFlower(near[g]);
                    res[g] = flower;
                    for(auto nxt : conn[g]) {
                        if(res[nxt] == 0) {
                            near[nxt] |= (1<<flower);
                            q.push(nxt);
                        }
                    }    
                }
            }
        }
        return res;
    }
};