- 科技
- 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
;
}
};
Processed:
0.015, SQL:
8
