1042. 不邻接植花

题目链接：1042. 不邻接植花

方法：位运算

解题思路

 根据题目可知，一个花园最多有 \(3\) 条边，因此每个花园一定可以有一个合适的种类，只需要与其邻接点的种类都不同即可，假设花的种类分别对应二进制位的第 \(1\)、\(2\)、\(3\)、\(4\)位（从低->高位），现在对于花园 \(u\)，计算其所有邻接点花园构成的掩码 \(mask\)，该花园花园的种类就等于其中某一位为 \(0\) 的那个种类。

代码

class Solution {
public:
    vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
        vector<vector<int>> adj(n + 1);
        for (auto &path : paths) {
            int u = path[0], v = path[1];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        vector<int> ans(n);
        for (int u = 1; u <= n; u ++ ) {
            int mask = 0;
            for (auto &v : adj[u]) mask |= 1 << ans[v - 1];
            for (int i = 1; i < 5; i ++ ) {
                if ((mask & (1 << i)) == 0) {
                    ans[u - 1] = i;
                    break;
                }
            }
        }

        return ans;
    }
};

复杂度分析

时间复杂度：\(O(n + m)\)；
空间复杂度：\(O(n + m)\)，邻接表的空间，\(n\) 个表头，存储 \(2m\) 条边。