给定一个具有N个顶点和E个边的图。边以U []和V []给出,这样对于每个索引i,U [i]连接到V [i]。任务是找到给定图形着色所需的最少颜色数。
例子
输入: N = 5,M = 6,U [] = {1,2,3,1,2,3},V [] = {3,3,4,4,5,5};输出: 3说明:对于上面的图形,节点1、3和5不能具有相同的颜色。因此,计数为3。
建议:在继续解决方案之前,请先在{IDE}上尝试使用您的方法。方法:我们将保留两个数组count []和colors []。数组count []将存储每个节点的边缘计数,而colors []将存储每个节点的颜色。将每个顶点的计数初始化为0,将每个顶点的颜色初始化为1。步骤:
为给定的一组边创建邻接表,并保留每个节点的边数遍历所有节点并将该节点插入没有边缘的队列Q中。当Q不为空时,请执行以下操作:从队列中弹出元素。对于连接到弹出节点的所有节点:减少弹出节点的当前边沿计数。如果当前颜色小于或等于其父级(弹出的节点)的颜色,则更新当前节点的颜色= 1 +弹出节点的颜色如果count为零,则将此节点插入队列Q中。colors []数组中的最大元素将给出给定图形着色所需的最小颜色数。