LeetCode笔记（图：图染色***）

1042. 不邻接植花

class Solution {
public:
    vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
        if(paths.empty()) return vector<int>(n, 1);

        vector<int> res(n, 0);
        vector<vector<int>> graph(n);
        for(auto x : paths) {
            graph[x[0] - 1].push_back(x[1] - 1);
            graph[x[1] - 1].push_back(x[0] - 1);
        }

        for(int i = 0; i < n; i++) {
            if(!res[i]) {
                unordered_set<int> colors{1, 2, 3, 4};
                for(auto x : graph[i]) {
                    if(res[x]) 
                        colors.erase(res[x]);
                }
                res[i] = *colors.begin();
            }
        }

        return res;
    }
};