難度：★★★☆☆
類型：圖
方法：貪心
題目
力扣鏈接請移步本題傳送門
更多力扣中等題的解決方案請移步力扣中等題目錄
有 n 個花園晒骇，按從 1 到 n 標記杉女。另有數(shù)組 paths 庆尘，其中 paths[i] = [xi, yi] 描述了花園 xi 到花園 yi 的雙向路徑地梨。在每個花園中瞬痘，你打算種下四種花之一伐庭。
另外顽照，所有花園 最多 有 3 條路徑可以進入或離開.
你需要為每個花園選擇一種花无畔，使得通過路徑相連的任何兩個花園中的花的種類互不相同。
以數(shù)組形式返回 任一 可行的方案作為答案 answer参袱，其中 answer[i] 為在第 (i+1) 個花園中種植的花的種類电谣』嗝罚花的種類用 1、2辰企、3风纠、4 表示。保證存在答案牢贸。
示例 1：
輸入：n = 3, paths = [[1,2],[2,3],[3,1]]
輸出：[1,2,3]
解釋：
花園 1 和 2 花的種類不同。
花園 2 和 3 花的種類不同镐捧。
花園 3 和 1 花的種類不同潜索。
因此，[1,2,3] 是一個滿足題意的答案懂酱。其他滿足題意的答案有 [1,2,4]竹习、[1,4,2] 和 [3,2,1]
示例 2：
輸入：n = 4, paths = [[1,2],[3,4]]
輸出：[1,2,1,2]
示例 3：
輸入：n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
輸出：[1,2,3,4]
提示：
1 <= n <= 104
0 <= paths.length <= 2 * 104
paths[i].length == 2
1 <= xi, yi <= n
xi != yi
每個花園 最多 有 3 條路徑可以進入或離開
解答
我們把花園看成結點，聯(lián)系各個結點的路徑用數(shù)組集合的方式給出列牺，很容易想到用深度優(yōu)先搜索或寬度優(yōu)先搜索的方法探索連通域整陌。
解法1：深度優(yōu)先搜索
第一步，建圖瞎领。
為了便于表達泌辫，我們把用字典的形式存儲每個結點的臨近結點。這里需要注意的是九默，為了便于python索引震放，我們把每個花園編號減1，將1到n范圍轉到了0到n-1范圍驼修。graph[node]是一個列表殿遂，里面是與node結點相鄰的所有結點。
第二步乙各，染色列表墨礁。
為了存儲每個花園的染色結果，我們準備一個列表color_of_耳峦，color_of_[node]表示node結點被染色的結果恩静，列表長度為n，默認值為0妇萄，每個位置將要被染色成1,2,3,4中的一個蜕企。
第三步，深度優(yōu)先搜索冠句。
定義深度優(yōu)先搜索函數(shù)實現(xiàn)循環(huán)染色轻掩。函數(shù)有兩個輸入，一個是結點node懦底，一個是該結點需要被染色的結果color唇牧，函數(shù)返回值是布爾量罕扎，表達能否成功染色。函數(shù)過程中執(zhí)行染色操作丐重。
入口處需要優(yōu)先判斷是否能被染色腔召，遍歷node的每個相鄰結點，如果發(fā)現(xiàn)任何一個相鄰結點已經(jīng)被染色為color扮惦，則染色失敗臀蛛，直接返回False。
如果通過了上面的校驗崖蜜，則可以將該結點染色浊仆，color_of_[node] = color，接下來就是把node的臨近結點neighbor染色豫领，這里需要注意顏色的選擇抡柿。我們需要選擇除了color以外的所有顏色，將這些顏色分別做嘗試等恐，一旦嘗試成功洲劣，則不再進行其他顏色的嘗試。臨近結點neighbor的選擇也有講究课蔬，如果該節(jié)點已經(jīng)被染了色囱稽，也就是該節(jié)點處color_of_對應位置處的值不是零，該節(jié)點是不需要再考慮的购笆。如果所有臨近結點都完成染色粗悯，則dfs返回值記得設置為True，代表node結點染色成功同欠。
第四步样傍，遍歷。
接下來就是使用dfs函數(shù)的時候铺遂。我們有必要遍歷每一個結點衫哥，一旦某結點沒有被染色（通過color_of_[node] 是否為零判斷），則調(diào)用dfs函數(shù)進行染色襟锐，顏色的選擇與上面類似撤逢，需要進行嘗試。
題目的解答過程實際上就是color_of_的填充過程粮坞，所有結點遍歷完成后蚊荣，如果發(fā)現(xiàn)color_of_中還有沒有被染色的結點，也就是0 in color_of_莫杈，則說明無法完成所有結點的染色互例，否則，直接返回染色結果筝闹。
編程中其他注意事項：
第一媳叨，為了給字典提供默認值腥光，我們使用defaultdict類；
第二糊秆，dfs函數(shù)的設計過程中武福，需要將終止條件寫在開頭。
from collections import defaultdict
class Solution:
def gardenNoAdj(self, n, paths):
graph = defaultdict(set)
for u, v in paths:
u, v = u - 1, v - 1
graph[u].add(v)
graph[v].add(u)
color_of_ = [0] * n
colors = {1, 2, 3, 4}
def dfs(node, color):
for neighbor in graph[node]:
if color_of_[neighbor] == color:
return False
color_of_[node] = color
for color in colors - {color}:
for neighbor in graph[node]:
if color_of_[neighbor] == 0 and dfs(neighbor, color):
return True
return True
for node in range(n):
if color_of_[node] == 0:
for color in colors:
if dfs(node, color):
break
if 0 in color_of_:
return "Unable for color!"
return color_of_
s = Solution()
print(s.gardenNoAdj(3, [[1,2],[2,3],[3,1]]))
print(s.gardenNoAdj(4, [[1,2],[3,4]]))
print(s.gardenNoAdj(4, [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]))
print(s.gardenNoAdj(5, [[1, 2], [1, 3], [1, 4], [1, 5],
[2, 3], [2, 4], [2, 5],
[3, 4], [3, 5],
[4, 5],
]))
解法2：貪心
因為題目已經(jīng)告訴了我們痘番，染色是一定可以成功的捉片，我們就可以直接放心的填充每一個結點了。最關鍵的填充什么顏色夫偶。對于某一個結點node界睁，其顏色需要根據(jù)臨近結點填充，而且有的臨近結點已經(jīng)被填充過了兵拢，有的沒有，我們只需要考慮被填充過的那些就好逾礁，需要保證該結點的顏色與那些已經(jīng)被填充過的結點顏色都不同说铃，至于到底填什么顏色，隨便彈出一個滿足條件的就夠了嘹履。只要每填充一個結點腻扇，都按照上面的法則，則填充結果一定是滿足要求的砾嫉。這樣在寫法上是非常簡單的幼苛。
python里通過集合相減的操作實現(xiàn)剩余顏色的獲取。
from collections import defaultdict
from typing import List
class Solution:
def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
graph = defaultdict(list)
for u, v in paths:
u, v = u - 1, v - 1
graph[u].append(v)
graph[v].append(u)
ans = [0] * n
for u in range(n):
colors = {1, 2, 3, 4} - set(ans[v] for v in graph[u])
ans[u] = colors.pop()
return ans
如有疑問或建議焕刮，歡迎評論區(qū)留言~
有關更多力扣中等題的python解決方案舶沿，請移步力扣中等題解析
