我刚刚开始阅读图论，并且正在阅读有关图着色的内容。我的脑海中浮现出这个问题：
我们必须仅用一种颜色对无向图（不完全）进行着色，以便使彩色节点的数量最大化。我们需要找到这个最大数量。我能够制定一种非循环图的方法：
我的方法：首先，我们将图划分为独立的组件，并对每个组件执行此操作。我们创建一个 dfs 树，并在遍历它时创建 2 个 dp 数组，以便根位于最后：
dp[0][u]=sum(dp[1][visited children])
dp[1][u]=sum(dp[0][visited children])
ans=max(dp[1][root],dp[0][root])
dp[0][i] , dp[1][i] are initialized to 0,1 respectively.
这里0表示无色，1表示有色。
但这对于循环图不起作用，因为我假设没有访问过的孩子是连接的。
有人可以指导我如何解决循环图的这个问题（而不是通过暴力）的正确方向吗？是否可以修改我的方法或者我们是否需要提出不同的方法？像为具有最少边缘的节点着色这样的贪婪方法会起作用吗？